• 注册
  • 关于作者
    个人说明:他太懒了,什么都没有写
    关注 0 粉丝 0 喜欢 0 内容 238
    雅安
    聊天 送礼
    • 查看作者
    • 排序算法

      为什么有这么多的排序算法?

      首先,在计算机编程中排序是一个经常遇到的问题。数据只有经过排序后,才更有意义。其次,排序算法说明了许多重要的算法的技术,例如二进制细分,递归和线性添加。最后要说明的一点是不同的算法有不同的优缺点,没有一种算法在任何情况下都是最好的算法。

      汽泡排序法

      该算法是专门针对已部分排序的数据进行排序的一种排序算法。如果在你的数据清单中只有一两个数据是乱序的话,用这种算法就是最快的排序算法。如果你的数据清单中的数据是随机排列的,那么这种方法就成了最慢的算法了。因此在使用这种算法之前一定要慎重。

      这种算法的核心思想是扫描数据清单,寻找出现乱序的两个相邻的项目。当找到这两个项目后,交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好。

      图1是对这种算法的说明。在该例中,数字1的未按顺序排好。第一次扫描清单时,程序找到4和1是两个相邻的乱序项目,于是交换它们的位置。以此类推,直到将所有的项目按1234排好。数字1就象上升的汽泡一样,这就是这一算法名称的由来。

      2 2 2 1
      3 3 1 2
      4 1 3 3
      1 4 4 4

      图1.

      你可以改进该算法,让程序自下而上开始扫描,这样只须一次就能排好顺序了。

      下面是用VB代码实现这一算法的例子:

      ' min and max are the minimum and maximum indexes
      ' of the items that might still be out of order.
      Sub BubbleSort (List() As Long, ByVal min As Integer, _
          ByVal max As Integer)
      Dim last_swap As Integer
      Dim i As Integer
      Dim j As Integer
      Dim tmp As Long
      
          ' Repeat until we are done.
          Do While min < max
              ' Bubble up.
              last_swap = min - 1
              ' For i = min + 1 To max
              i = min + 1
              Do While i <= max
                  ' Find a bubble.
                  If List(i - 1) > List(i) Then
                      ' See where to drop the bubble.
                      tmp = List(i - 1)
                      j = i
                      Do
                          List(j - 1) = List(j)
                          j = j + 1
                          If j > max Then Exit Do
                      Loop While List(j) < tmp
                      List(j - 1) = tmp
                      last_swap = j - 1
                      i = j + 1
                  Else
                      i = i + 1
                  End If
              Loop
              ' Update max.
              max = last_swap - 1
      
              ' Bubble down.
              last_swap = max + 1
              ' For i = max - 1 To min Step -1
              i = max - 1
              Do While i >= min
                  ' Find a bubble.
                  If List(i + 1) < List(i) Then
                      ' See where to drop the bubble.
                      tmp = List(i + 1)
                      j = i
                      Do
                          List(j + 1) = List(j)
                          j = j - 1
                          If j < min Then Exit Do
                      Loop While List(j) > tmp
                      List(j + 1) = tmp
                      last_swap = j + 1
                      i = j - 1
                  Else
                      i = i - 1
                  End If
              Loop
              ' Update min.
              min = last_swap + 1
          Loop
      End Sub

      选择排序法 选择排序法是一个很简单的算法。其原理是首先找到数据清单中的最小的数据,然后将这个数据同第一个数据交换位置;接下来找第二小的数据,再将其同第二个数据交换位置,以此类推。下面是VB代码实现该算法。

      VB填充IE上的输入框并提交

      VB学习

      Sub Selectionsort (List() As Long, min As Integer, _
          max As Integer)
      Dim i As Integer
      Dim j As Integer
      Dim best_value As Long
      Dim best_j As Integer
      
          For i = min To max - 1
              best_value = List(i)
              best_j = i
              For j = i + 1 To max
                  If List(j) < best_value Then
                      best_value = List(j)
                      best_j = j
                  End If
              Next j
              List(best_j) = List(i)
              List(i) = best_value
          Next i
      End Sub

      当寻找第I小的数据时,你必须检查N-I个项目,所以这一算法所用的步骤可用下面这个公式求得。

       N + (N - 1) + (N - 2) + ... + 1 = N * (N + 1) / 2

      选择排序法适用于较少数据的排序。此外由于算法较简单,因此他的代码也比较简单,这就为我们维护代码带来了方便。实际上如果你的数据相当少的话,这种算法的速度快过其它更复杂的算法。

      快速排序法

      快速排序法对于大量数据的排序特别有用。其基本原理是:首先检查数据列表中的数据数,如果小于两个,则直接退出程序。如果有超过两个以上的数据,就选择一个分割点将数据分成两个部分,小于分割点的数据放在一组,其余的放在另一组,然后分别对两组数据排序。

      通常分割点的数据是随机选取的。这样无论你的数据是否已被排列过,你所分割成的两个字列表的大小是差不多的。而只要两个子列表的大小差不多,该算法所需的步骤就是N * log(N) 步。对于使用比较法进行排序的算法来讲这是最快的方法。下面是用VB代码实现这一算法的例子。

      Sub Quicksort (List() As Long, min As Integer, max As Integer)
      Dim med_value As Long
      Dim hi As Integer
      Dim lo As Integer
      Dim i As Integer
      
          ' If the list has no more than 1 element, it's sorted.
          If min >= max Then Exit Sub
      
          ' Pick a dividing item.
          i = Int((max - min + 1) * Rnd + min)
          med_value = List(i)
      
          ' Swap it to the front so we can find it easily.
          List(i) = List(min)
      
          ' Move the items smaller than this into the left
          ' half of the list. Move the others into the right.
          lo = min
          hi = max
          Do
              ' Look down from hi for a value < med_value.
              Do While List(hi) >= med_value
                  hi = hi - 1
                  If hi <= lo Then Exit Do
              Loop
              If hi <= lo Then
                  List(lo) = med_value
                  Exit Do
              End If
      
              ' Swap the lo and hi values.
              List(lo) = List(hi)
              
              ' Look up from lo for a value >= med_value.
              lo = lo + 1
              Do While List(lo) < med_value
                  lo = lo + 1
                  If lo >= hi Then Exit Do
              Loop
              If lo >= hi Then
                  lo = hi
                  List(hi) = med_value
                  Exit Do
              End If
      
              ' Swap the lo and hi values.
              List(hi) = List(lo)
          Loop
      
          ' Sort the two sublists
          Quicksort List(), min, lo - 1
          Quicksort List(), lo + 1, max
      End Sub

      计数排序法

      前面提到过,对于使用比较法作为算法基础的算法来说,最快需N * log(N)步才能完成排序。计数排序法不作用比较,所以它不受此限制。实际上该算法是如此之快,以致于你会认为是使用了魔术,而不是数学运算来排序。

      另一方面,计数排序法只能用于特殊的情况。首先,所有的要进行排序的数据必须是整数,不能对字符使用该算法;其次,数据的范围有限,如果你的数据是在1到1000之内,用这种算法的效果就非常好,但如果你的数据是在1到30000之间,该算法就根本不能用。

      首先该算法创建一个整数类型的临时数组,该数组的上下标分别是要排序的数据的最大最小值。如果数据列表的最大最小值从min_item到max_item, 该算法就将数组创建成下面这样:

       Dim Counts() As Integer ReDim Counts(min_item To max_item)

      接下来,算法检查列表中的每一个项目,并增加对应该项目的数组元素的值,当这一阶段完成后,Counts(I)的数值就是就是数值为I的基础上的个数。

          For I = min To Max
              Counts(List(I)) = Counts(List(I)) + 1
          Next I

      程序扫描Counts数组,将counts转换成被排序列表中的偏移量。

          next_spot = 1
          For i = min_value To max_value
              this_count = counts(i)
              counts(i) = next_spot
              next_spot = next_spot + this_count
          Next i

      最后将数据进行排序

      下面是实现该算法的VB代码

      Sub Countingsort (List() As Long, sorted_list() As Long, _
          min As Integer, max As Integer, min_value As Long, _
          max_value As Long)
      Dim counts() As Integer
      Dim i As Integer
      Dim this_count As Integer
      Dim next_offset As Integer
      
          ' Create the Counts array.
          ReDim counts(min_value To max_value)
      
          ' Count the items.
          For i = min To max
              counts(List(i)) = counts(List(i)) + 1
          Next i
      
          ' Convert the counts into offsets.
          next_offset = min
          For i = min_value To max_value
              this_count = counts(i)
              counts(i) = next_offset
              next_offset = next_offset + this_count
          Next i
      
          ' Place the items in the sorted array.
          For i = min To max
              sorted_list(counts(List(i))) = List(i)
              counts(List(i)) = counts(List(i)) + 1
          Next i
      End Sub

      总结

      下表是各种算法的优缺点比较,正如你所见到的那样,每种算法只是在某一情况下表现得最好,下面是选择算法时的一些原则:

      • 如果你的数据列表中有99%数据已排过序,则用汽泡排序法。
      • 如果你要排序的数据较少(100个以下),则用选择排序法。
      • 如果你的数据都是整数,并且数值不大(几千以内),则用计数排序法。
      • 否则的话用快速排序法法
      算法 优点 缺点
      汽泡排序法 对以初步排序的数据来说这种方法的速度很快 在其它情况下运行速度较慢
      选择排序法 非常简单 对大量数据的排序速度很慢
      容易明白
      对于少量数据的排序来说速度很快
      快速排序法 对大量数据的排序来说速度很快 如果有大量重复的数据就比较麻烦
      计数排序法 当数据数值较小(1-1000之间)时,速度非常快 当数据数值较大时,速度较慢
      需额外的内存
      只能对整数类型的数据排序

      利用Visual Basic操作XML数据

      VB学习

    • 0
    • 0
    • 0
    • 44
    • 单栏布局 侧栏位置: