VB排序算法概要

1、为什么有这么多的排序算法？首先,在计算机编程中排序是一个经常遇到的问题。数据只有经过排序后，才更有意义。其 次,排序算法说明了许多重要的算法的技术，例如二进制细分，递归和线 性添加。最后要说明的一点是不同的算法有不同的优缺点，没有一种算法在任何情 况下都是最好的算法。 汽泡排序法该算法是专门针对已部分排序的数据进行排序的一种排序算法。 如果在你的 数据清单中只有一两个数据是乱序的话，用这种算法就是最快的排序算法。如果你的数据清单中的数据是随机排列的,那么这种方法就成了最慢的算法了。因此在使 用这种算法之前一定要慎重。这种算法的核心思想是扫描数据清单，寻找出现乱序 的两个相邻的项目。当找到这两个

2、项目 后，交换项目的位置然后继续扫描。重复上 面的操作直到所有的项目都按顺序排好。图1是对这种算法的说明。在该例中，数字1的未按顺序排好。第一次扫描清单时，程序找到4和1是两个相邻的乱序项目 于是交换它们的位置。以此类推，直到将所有的项目按1234排好。数字1就象上升 的汽泡一样，这就是这一算法名称的由来。2221331241331444图1.你可以改进该算法，让程序自下而上开始扫描，这样只须一次就能排好顺序了。下面是用VB代码实现这一算法的例子：min and max are the minimum and maximum in dexesof the items that might st

3、ill be out of order.Sub BubbleSort (List( As Long, ByVai min As Integer, _ByVai max As In tegerDim last_swap As In tegerDim i As In tegerDim j As In tegerDim tmp As LongRepeat un til we are done.Do While min maxBubble up.last_swap = min - 1For i = min + 1 To maxi = min + 1Do While i List(i The nSee

4、where to drop the bubble.tmp = List(i - 1DoList(j - 1 = List(jj = j + 1If j max Then Exit DoLoop While List(j = minFind a bubble.If List(i + 1 List(i The nSee where to drop the bubble.tmp = List(i + 1j = iDoList(j + 1 = List(jj = j - 1If j tmpList(j + 1 = tmplast_swap = j + 1i = j - 1Elsei = i - 1En

5、d IfLoopUpdate mi n.min = last_swap + 1End IfLoopEnd Sub选择排序法 选择排序法是一个很简单的算法。其原理是首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来找第二小的数据，再 将其同第二个数据交换 位置,以此类推。下面是VB代码实现该算法。Sub Select ion sort (List( As Long, min As In teger, _max As In tegerDim i As In tegerDim j As In tegerDim best_value As LongDim best_j As I

6、n tegerFor i = min To max - 1best_value = List(ibest_j = iFor j = i + 1 To maxIf List(j = max Then Exit SubPick a dividi ng item.i = Int(max - min + 1 * Rnd + minmed_value = List(iSwap it to the front so we can find it easily. List(i = List(minMove the items smaller than this into the left half of t

7、he list. Move the others into the right. lo = minhi = maxDoLook dow n from hi for a value = med_valuehi = hi - 1If hi = lo Then Exit DoLoopIf hi = med_value. Io = Io + 1Do While List(lo = hi Then Exit DoLoopIf lo = hi The nlo = hiList(hi = med_valueExit DoEnd IfSwap the lo and hi values.List(hi = Li

8、st(loLoopSort the two sublistsQuicksort List(, min, lo - 1Quicksort List(, lo + 1, max计数排序法前面提到过，对于使用比较法作为算法基础的算法来说，最快需N * log(N步才 能完成排序。计数排序法不作用比较，所以它不受此限制。实际上该算法是如此之 快,以致于你会认为是 使用了魔术，而不是数学运算来排序。另一方面，计数排序法只能用于特殊的情况。首先，所有的要进行排序的数据必 须是整数,不能对字符使用该算法；其次，数据的范围有限，如果你的数据是在1到 1000之内,用这种算法的效果就非常好,但如果你的数据是在1

9、到30000之间该算 法就根本不能用。首先该算法创建一个整数类型的临时数组，该数组的上下标分别 是要排序的数据的最大最小值。如果数据列表的最大最小值从min_item到 max_item,该算法就将数组创建成下面这样：Dim Cou nts( As In tegerReDim Counts(min_item To max_item接下来，算法检查列表中的每一个项目，并 增加对应该项目的数组元素的值，当这一阶段完成后，Counts(l的数值就是就是数值 为I的基础上的个数。For I = min To MaxCou nts(List(I = Cou nts(List(I + 1Next I程序扫

10、描Counts数组将counts转换成被排序列表中的偏移量。n ext_spot = 1For i = min _value To max_valuethis_co unt = coun ts(icoun ts(i = n ext_spotn ext_spot = n ext_spot + this_c ountNext i最后将数据进行排序F面是实现该算法的VB代码Sub Coun ti ngsort (List( As Long, sorted_list( As Long, _ min As Integer, max As Integer, min_value As Long, _ max

11、_value As LongDim coun ts( As In tegerDim i As In tegerDim this_co unt As In tegerDim n ext_offset As In tegerCreate the Counts array.ReDim coun ts( min _value To max_valueCount the items.For i = min To maxcoun ts(List(i = coun ts(List(i + 1Next iCon vert the counts into offsets.n ext_offset = minFo

12、r i = min _value To max_valuethis_co unt = coun ts(icoun ts(i = n ext_offsetnext_offset = next_offset + this_count Next i Place the items in the sorted array.For i = min To max sortedist(co un ts(List(i = List(i coun ts(List(i = coun ts(List(i + 1Next i End Sub总结下表是各种算法的优缺点比较，正如你所见到的那样， 每种算法只是在某一情况下表现得最好，下面是选择算法时的一些原则：如果你的数 据列表中有99%数据已排过序，则用汽泡排序法。如果你要排序的数据较少(100个以下，则用选择排序法。如果你的数据都是整数，并且数值不大(几千以内，则用计数排序法。否则的话用快速排序法法