本帖最后由 lee1892 于 2013-4-17 09:45 编辑
一些说明
由于论坛设置了编辑帖子的时限,而我写帖子喜欢不断加新内容,所以这个帖子就不再设顶楼目录了。
另外,这个帖子内容会比较多,所以我估计发帖的时间跨度会比较大。考虑到期间别人的回帖,那么我发的帖子会比较分散,建议看贴的时候可以点击 只看该作者 。
前言
顾名思义,所谓排序算法(Sorting Algorithm)就是将一组数据按某种特定的顺序重新排列组织。显然,这一需要是我们在日常处理工作当中总是要用到的。这也是排序算法是计算机世界中最为重要的算法的原因。最为常见的顺序是 数值顺序 和 字符顺序。对于一些其它算法的优化,一个高效的排序算法是起决定性作用的,比如查找、合并等。
排序算法的分类与评价
- 计算复杂度(Computational Complexity),包括最坏、平均、最佳情况,通常由数据元素的数量(n)来计算,而用大O符号来表达。理想的计算复杂度是 O(n),但一般而言,好的性能是 O(n log n),平均性能是 O(log^2 n)。
- 空间使用(Memory Usage),指除了待排序的源数据外,算法所需的额外的临时存储空间。通常将不使用或使用有限个(常数)元素O(1)额外空间的排序算法,称为原地排序算法(In Place Sorting),比如冒泡排序。
- 稳定性(Stability),如果一个排序算法对于源数据中两个排序关键值相同的元素,在排序后不改变其原有顺序的,则称这个排序算法是稳定的。比如以下对(2, 9) (1, 3) (2, 7) (3, 4)四个数字对按第一个数字排序时,稳定的算法则会得到 (1, 3) (2, 9) (2, 7) (3, 4),而不稳定的算法则会得到 (1, 3) (2, 7) (2, 9) (3, 4)。
- 是否使用递归,通常程序语言都会对递归寄存器有所限制,一些早期的语言甚至不支持递归。
- 是否对比,多数的排序算法都会进行元素间的对比,但也有些算法是不用对比的,如计数排序。
- 排序方式,包括 插入、交换、选择、合并 等等。
排序方式 | 排序算法 | 交换排序(Exchange Sort) | 冒泡排序(Bubble Sort) 鸡尾酒排序(Cocktail Sort) 快速排序(Quick Sort) 梳排序(Comb Sort) ... | 选择排序(Selection Sort) | 选择排序(Selection Sort) 堆排序(Heap Sort) ... | 插入排序(Insertion Sort) | 插入排序(Insertion Sort) 希尔排序(Shell Sort) 二叉查找树排序(Binary Tree Sort) ... | 合并排序(Merge Sort) | 合并排序(Merge Sort) ... | 分配排序(Distribution Sort) | 计数排序(Counting Sort) 基数排序(Radix Sort) 桶排序(Bucket Sort) ... | 并发排序(Concurrent Sort) | ... | 混合排序(Hybrid Sort) | 内省排序(Introsort) ... | 其它 | ... | 本帖最后由 lee1892 于 2013-4-18 08:31 编辑
大O符号(Big O Notation)
在开始讨论具体算法之前,有必要先说明一下这个大O符号的含义。
大O符号是用于描述函数渐近行为的数学符号,它是用另一个更简单的函数来描述一个函数数量级的上界。在计算机世界中,用来分析算法复杂性。
在数学中,一个函数自变量或则向无穷大驱近或则向无穷小驱近,也就相应的存在大O符号的无穷大渐近和无穷小渐近。然而在计算机世界中,当我们用来分析算法复杂性时,这一函数自变量通常是一系列数据元素的数量,比如排序算法中待排序的元素数量、商人旅行问题中城市的数量等,显然其对应的是无穷大渐近。
以冒泡排序为例,待排序元素数量为 n(或称问题的规模为 n),那么元素间进行对比判断的次数 T(n) = (n - 1)^2 = n^2 - 2n + 1
当 n 向无穷大渐近时,n^2项会占主导地位,比如当 n=10000 时,n^2 项是 2n 项的5000倍,这时省略后者对 T(n) 的值的影响在数量级的考量上可以忽略,那么就可以将冒泡排序的算法复杂度表达为 O(n^2)。
再进一步,如果 T(n) = 4(n - 1)^2 = 4n^2 - 8n + 4,n^2项的系数4在数量级的考量上也是无关紧要的。以 T(n) 自身的比较,即便这个系数非常大,比如是100'000,当 n 足够大时(比如 1'000'000)时,该系数对结果的影响也是可以忽略的。又或则比较两个函数 T(n) = 100'000 * n^2 和 R(n) = n^3,当 n 足够大时(比如1'000'000'000),后者总是远远超过前者。所以我们称 T(n) = 4(n - 1)^2 的时间复杂度也同样的是 O(n^2)。
需要指出的是,在计算机世界中所谓的算法复杂性是指某个主要操作的重复,也就意味着计算时间的消耗,或称时间复杂度。
常见的函数阶(算法复杂度) 以下函数阶由小至大排列,n 为函数自变量,c 为一个常数,log 为2为底的对数。
符号 | 名称 | 备注 | O(1) | 常数(阶) | 如果某算法的主要操作重复4次,也是用 O(1)表达,而不会是 O(4)。 | O(log^c n) | 迭代对数(阶) | c=2 -> log (log n) | O(log n) | 对数(阶) | | O[(log n)^c] | 多对数(阶) | | O(n) | 线性(阶) | | O(n log n) | 线性对数(阶) | | O(n^2) | 平方(阶) | | O(n^c) | 多项式(阶) | c=2 时,即为平方阶 | O(c^n) | 指数(阶) | | O(n!) | 阶乘(阶) |
|
本帖最后由 lee1892 于 2013-4-20 13:14 编辑
基础的排序算法
名称 | 稳定性 | 最佳时间复杂度 | 平均时间复杂度 | 最差时间复杂度 | 空间复杂度 | 排序方式 | 冒泡排序 | 是 | O(n) | O(n^2) | O(n^2) | O(1) | 交换 | 选择排序 | 否 | O(n^2) | O(n^2) | O(n^2) | O(1) | 选择 | 插入排序 | 是 | O(n) | O(n^2) | O(n^2) | O(1) | 插入 |
注:所有示例代码均设 Optional Base 1
运作方式: 1、比较相邻的两个元素,按所需顺序决定是否交换。 2、对每一对相邻元素进行同样的工作,从第一对至最后一对。结束后,最后一个元素应该是所需顺序的最值(如所需顺序为由小至大,则为最大值)。 3、对所有元素重复上述步骤,除了最后一个。 4、重复前述步骤,称前部分需要对比的为无序区,后部分不需要对比的为有序区,直到无序区仅剩一个元素。 [code=vb]Sub BubbleSort(ByRef arr) Dim i&, j&, vSwap For i = UBound(arr) To 2 Step -1 For j = 1 To i - 1 If arr(j) > arr(j + 1) Then vSwap = arr(j): arr(j) = arr(j +1): arr(j + 1) = vSwap End If Next Next End Sub[/code] 注:有别于坛子里很多人的习惯的由小至大的双循环(如下),真正的冒泡总是在一次循环后将最值元素冒泡式的置于有序区。 [code=vb]For i = 1 To UBound(arr) - 1 For j = i + 1 To UBound(arr) If arr(i) > arr(j) Then vSwap = arr(i): arr(i) = arr(j): arr(j) = vSwap Next Next[/code]
运作方式: 1、对(无序区)全部元素由前至后扫描,找出最值。 2、将最值元素与(无序区)第一个元素交换,此时前端为有序区,后端为无序区。 3、重复上述步骤,直到无序区仅剩一个元素。 [code=vb]Sub SelectionSort(ByRef arr) Dim i&, j&, vSwap, min& For i = 1 To UBound(arr) - 1 min = i For j = i + 1 To UBound(arr) If arr(min) > arr(j) Then min = j Next If min <> i Then vSwap = arr(min): arr(min) = arr(i): arr(i) = vSwap End If Next End Sub[/code]
运作方式: 1、全部元素同样的分为有序区在前和无序区在后,开始时有序区仅有第一个元素。 2、取无序区的第一个元素,与有序区中元素由后至前扫描对比。 3、将该元素插入至正确位置,该位置(含)之后的有序区元素向后移位,将该位置赋值为该元素。 4、重复上述步骤,直至无序区仅剩一个元素。 [code=vb]Sub InsertionSort(ByRef arr) Dim i&, j&, vTemp For i = 2 To UBound(arr) vTemp = arr(i) For j = i To 2 Step -1 If arr(j - 1) < vTemp Then Exit For arr(j) = arr(j-1) Next arr(j) = vTemp Next End Sub[/code] 以下是对数组(9, 6, 13, 7, 14, 2, 4, 3, 1, 8, 10, 11, 5, 16, 15, 12)使用不同方法排序的可视化图。
|
本帖最后由 lee1892 于 2013-4-20 10:51 编辑
进阶的排序算法
名称 | 稳定性 | 最佳时间复杂度 | 平均时间复杂度 | 最差时间复杂度 | 空间复杂度 | 排序方式 | 合并排序 | 是 | O(n log n) | O(n log n) | O(n log n) | O(n) | 合并 | 堆排序 | 否 | O(n log n) | O(n log n) | O(n log n) | O(1) | 选择 | 快速排序 | 否 | O(n log n) | O(n log n) | O(n^2) | O(log n) 堆栈空间 | 交换 | 希尔排序 | 否 | O(n) | O[n (log n)^2] 或 O(n^1.5) | O[n (log n)^2] | O(1) | 插入 |
运作方式: 1、合并排序是基于合并操作的一种算法,所谓合并操作是指将两组有序数据合并为一个有序数据的操作。其实现方式是: a、申请足够的结果数据存储空间; b、设置两个指针分别指向两组有序数据的第一个元素; c、比较两个指针指向的元素,按所需顺序,将其中一个存至结果空间,并向后移动该指针; d、重复上一步操作,直至某一个指针为空(该组数据全部移动完成); e、将剩余的数据顺序存至结果空间。 2、其具体的实现,又可分为两种方式:由上至下、由下至上。 3、由上至下,递归过程: a、将待排序数据均分为两组,称为左、右 b、分别将左右两组数据作为待排序数据代入步骤a,分为两组 c、重复上述操作,直至待排序数据仅剩一个元素 d、合并左右两组数据,递归 4、由下至上,迭代过程: a、视单个元素为一组有序数据,则全部数据可视为数量为元素数量个的有序数据 b、将前后两个有序数据合并为一个新的有序数据,有序数据的数量减半 c、重复上述步骤,直至仅剩一个有序数据
由上至下的VBA实现: [code=vb]Sub MergeSort_UpDown(ByRef arr) Dim nLen&, nMid&, aLeft, aRight, i& nLen = UBound(arr) If nLen <=1 Then Exit Sub ' 如果数组长度为1,则退出 nMid = Int(nLen / 2) ReDim aLeft(1 To nMid) ReDim aRight(1 To nLen - nMid) For i = 1 To nMid aLeft(i) = arr(i) Next For i = nMid + 1 To nLen aRight(i - nMid) = arr(i) Next Call MergeSort_UpDown(aLeft) Call MergeSort_UpDown(aRight) Call Merge(arr, aLeft, aRight) End Sub
Private Sub Merge(ByRef arr, ByRef aLeft, ByRef aRight) Dim i&, aTemp, nLeftLen&, nRightLen&, nLeftInd&, nRightInd&, nTempInd& nLeftLen = UBound(aLeft): nRightLen = UBound(aRight) ReDim aTemp(1 To nLeftLen + nRightLen) nLeftInd = 1: nRightInd = 1: nTempInd = 1 Do While nLeftInd <= nLeftLen And nRightInd <= nRightLen If aLeft(nLeftInd) < aRight(nRightInd) Then aTemp(nTempInd) = aLeft(nLeftInd) nLeftInd = nLeftInd + 1 Else aTemp(nTempInd) = aRight(nRightInd) nRightInd = nRightInd +1 End If nTempInd = nTempInd +1 Loop If nLeftInd <= nLeftLen Then For i = nLeftInd To nLeftLen aTemp(nTempInd) = aLeft(i) nTempInd = nTempInd + 1 Next End If If nRightInd <= nRightLen Then For i = nRightInd To nRightLen aTemp(nTempInd) = aRight(i) nTempInd = nTempInd + 1 Next End If
arr = aTemp End Sub[/code]
由下至上的VBA实现: [code=vb]Sub MergeSort_BottomUp(ByRef arr) Dim i&, nLen&, aTemp Dim nLeftMin&, nLeftMax&, nRightMin&, nRightMax&, nNext& nLen = UBound(arr) ReDim aTemp(1 To nLen) i = 1 Do While i <= nLen nLeftMin = 1 Do While nLeftMin <= nLen - i nLeftMax = nLeftMin + i nRightMin = nLeftMax nRightMax = nLeftMax + i If nRightMax > nLen Then nRightMax = nLen + 1 nNext = 1 Do While nLeftMin < nLeftMax And nRightMin < nRightMax If arr(nLeftMin) > arr(nRightMin) Then aTemp(nNext) = arr(nRightMin) nRightMin = nRightMin + 1 Else aTemp(nNext) = arr(nLeftMin) nLeftMin = nLeftMin + 1 End If nNext = nNext + 1 Loop Do While nLeftMin < nLeftMax nRightMin = nRightMin - 1 nLeftMax = nLeftMax - 1 arr(nRightMin) = arr(nLeftMax) Loop Do While nNext > 1 nRightMin = nRightMin - 1 nNext = nNext - 1 arr(nRightMin) = aTemp(nNext) Loop nLeftMin = nRightMax Loop i = i * 2 Loop End Sub[/code]
下图为由下至上的合并算法可视化图:
|
运作方式: 顾名思义,所谓堆排序是利用堆这个数据结构来进行排序。我们知道堆顶是堆中数据的最值元素,那么不断的从堆顶提出元素并顺序的放置数据中就可以得到一个有序数据。最为常用的是二叉堆排序。关于堆的讨论,可参考我的数据结构的帖子。
1、将源数据进行二叉堆转化,此时堆数据长度为源数据长度。 2、将整个数据视为两个部分,前半部分为二叉堆(此时堆数据长度为源数据长度),后半部分为有序区(此时长度为0)。 3、交换堆顶元素和堆底元素,二叉堆长度-1,有序区长度+1,维护二叉堆。 4、重复上一步操作,直至二叉堆长度为1。
[code=vb]Sub HeapSort(ByRef arr) Dim i&, nLen&, vSwap nLen = UBound(arr) For i = Int(nLen / 2) To 1 Step -1 Call Heapfy(arr, i, nLen) Next For i = 1 To nLen - 1 vSwap = arr(1): arr(1) = arr(nLen - i + 1): arr(nLen - i + 1) = vSwap Call Heapfy(arr, 1, nLen - i) Next End Sub
Private Sub Heapfy(ByRef arr, ByVal nInd&, ByVal nLen&) Dim nChd&, vSwap nChd = nInd * 2 Do While nChd < nLen If nChd + 1 < nLen And arr(nChd) < arr(nChd + 1) Then nChd = nChd + 1 If arr(nInd) > arr(nChd) Then Exit Do vSwap = arr(nChd): arr(nChd) = arr(nInd): arr(nInd) = vSwap nInd = nChd nChd = nInd * 2 Loop End Sub[/code]
二叉堆i排序的可视化图:
运作方式: 快速排序与二叉查找树基于一样的思路,采用了分治(Divide & Conquer)的策略。 1、选择一个元素作为比较的基准(Pivot)。 2、将所有元素与基准逐个对比,按所需顺序置于基准的两侧,如升序排列时大的放在基准右侧、小的放在左侧,将整个数据划分为左右两个分区。 3、视左右两个分区为两个单独的待排序数据,递归的重复上述操作,直至分区中元素只有一个。
取分区第一个元素作为基准的VBA实现,调用时 nLeft=LBound(arr): nRight=UBound(arr): [code=vb]Sub QuickSort(ByRef arr, ByRef nLeft&, ByRef nRight&) Dim i&, j&, vKey, vSwap If nLeft >= nRight Then Exit Sub vKey = arr(nLeft) i = nLeft + 1: j = nRight Do Do While i <= nRight If arr(i) > vKey Then Exit Do i = i + 1 Loop Do While j > nLeft If arr(j) < vKey Then Exit Do j = j - 1 Loop If i >= j Then Exit Do vSwap = arr(i): arr(i) = arr(j): arr(j) = vSwap Loop If nLeft <> j Then vSwap = arr(nLeft): arr(nLeft) = arr(j): arr(j) = vSwap End If If nLeft < j Then Call QuickSort(arr, nLeft, j) If j + 1 < nRight Then Call QuickSort(arr, j + 1, nRight) End Sub[/code]
快速排序的可视化图:
|
本帖最后由 lee1892 于 2013-4-24 14:36 编辑 希尔排序是插入排序的一个优化。在插入排序中,每次对比是由后前逐个对比,或言对比的步长为1。有个叫Donald Shell的家伙提出,对比的步长可由大至小,直至步长为1变为插入排序。这样一来在最初的几个对比步长中,较小的元素(假设按升序排序)就会向目标位置前进一大步。 运作方式: 1、设置步长序列,由大至小。 2、由步长序列中,逐个获取步长。 3、由源数据中第步长+1个元素向后扫描,作为基准值。 4、由步骤3中的基准值元素向前扫描与基准值对比,并进行必要的位移,同时每次递减为步长而不是1。 5、将基准值插入到正确的位置。 6、重复2、3、4、5,直至步长为1。 插入排序 | 希尔排序 | [code=vb]Sub InsertionSort(ByRef arr) Dim i&, j&, vTemp
For i = 2 To UBound(arr) vTemp = arr(i) For j = i To 2 Step -1 If arr(j - 1) < vTemp Then Exit For arr(j) = arr(j-1) Next arr(j) = vTemp Next
End Sub[/code] | [code=vb]Sub ShellSort(ByRef arr) Dim i&, j&, vTemp, aGaps, nGap, nLen& aGaps = Array(701, 301, 132, 57, 23, 10, 4, 1) nLen = UBound(arr) For Each nGap In aGaps For i = nGap + 1 To nLen vTemp = arr(i) For j = i To nGap + 1 Step nGap * -1 If arr(j - nGap) < vTemp Then Exit For arr(j) = arr(j - nGap) Next arr(j) = nTemp Next Next End Sub[/code] |
希尔排序的可视化图: 最初Shell提出的步长序列是 k = n/2,即由数据长度的一半开始,每次减半,但很快就被证明是个非常不怎么样的序列。以下是一些已经被证明非常好的步长序列: 公式 | 序列数值 | 最坏情况的时间复杂度 | 作者/年份 | 9 * [4 ^ (k - 1) - 2 ^ (k - 1)] + 1 4 ^ (k + 1) - 6 * 2 ^ k + 1 | 1, 5, 19, 41, 109, ... | O[n ^ (4/3)] | Sedgewick/1986 | 4 ^ k + 3 * 2 ^ (k - 1) + 1 | 1, 8, 23, 77, 281, ... | O[n ^ (4/3)] | Sedgewick/1986 | INT{(9 ^ k - 4 ^ k) / [ 5 * 4 ^ (k - 1)]} + 1 | 1, 4, 9, 20, 46, 103, ... | 未知 | Tokuda/1992 | 未知 | 1, 4, 10, 23, 57, 132, 301, 701 | 未知 | Ciura/2001 | 费波那契数列除去0和1将剩余的数 以黄金分区比的两倍的幂进行运算得到的数列 | 1, 9, 34, 182, 836, 4025, 19001, ... | 未知 | 在大数组中有优异表现 |
值得指出的是,希尔排序通常只在数量较小的数组中表现较好,但通常的对于大量数据而言希尔排序比快速排序慢。 本帖最后由 lee1892 于 2013-4-20 16:22 编辑 基于比较的排序算法的小结以上排序算法的附件: 排序算法初探_By Lee1892.rar(30.72 KB, 下载次数: 403)- 关于合并排序
合并排序也是基于分治思路的一种排序算法。它是唯一的具有O(n log n)最差时间复杂度的稳定的排序算法。由于其采用了明确的分治方法,合并排序可以非常容易的实现并行计算,对于多核心或多CPU的系统而言,并行计算能够极大的加快执行速度,其并行设计可既应用在由上至下的分区阶段,也可同时应用在合并阶段。另外,合并排序通常是对链表排序的最佳选择,相较而言,快速排序应用在链表上表现非常差,而堆排序则几乎无法实现。合并排序也被广泛用于慢介质存储器上。 - 关于堆排序
堆排序作为具有O(n log n)最差时间复杂度的排序算法也被广泛应用,它不像快速排序有退化至O(n ^ 2)的可能。内省排序(Introsort)就是结合使用了快速排序和堆排序来实现的,这种结合不同排序算法的实现就被称为混合排序。 - 关于快速排序
快速排序有着最佳的平均时间复杂度,对于一个乱序数据而言,是最佳的选择。但快速排序有退化至O(n ^ 2)的可能,使得其存在安全上的风险。另外,快速排序使用了递归,可能会大量占用递归堆栈空间,甚至造成溢出。在实际使用中,通常都会对快速排序作优化:结合其它排序算法(如在数据数量小于一定个数时,直接采用插入排序)、选择合适的基准值(如随机选择)、采用3分区法(3-Way Quick Sort)等。当前大多数流行的程序语言中都有内置的Sort方法,通常都是使用的快速排序法的优化。 - 关于希尔排序
希尔排序虽然在较小的数据量时有着较快的速度,但在实际应用中却很少使用。偶尔被一些混合排序算法使用在较小数据数量情况下,作为避免及减少递归次数。
对一个排序算法的评价,除了上述的时间、空间复杂度以及稳定性等因素外,还要考量其对不同特征的源数据的排序效果。通常这样的考量针对情况是:乱序、已基本排序、完全倒序、有很多重复值等情况。参考网站: http://www.sorting-algorithms.com单纯的评价某个排序算法最佳从来都不是一个明智的事情。 楼上的点评还真敢写~~居然还冒出个彭氏算法,Sigh~~~本帖最后由 lee1892 于 2013-4-20 16:21 编辑 分配排序算法所谓分配排序,就是将源数据的元素分配到有序的空间内,显然这样的方式会用到较大的空间,但极大的降低了时间复杂度。 如果源数据待排序的关键值是较小的整数的话,就可以通过统计关键值的数量来进行排序。 [code=vb]Sub CoutingSort(ByRef arr&()) Dim i&, j&, aTemp&(), nMin&, nMax&, nInd& nMin = arr(LBound(arr)): nMax = nMin For i = LBound(arr) + 1 To UBound(arr) If arr(i) < nMin Then nMin = arr(i) If arr(i) > nMax Then nMax = arr(i) Next ReDim aTemp(nMin To nMax) For i = LBound(arr) To UBound(arr) aTemp(arr(i)) = aTemp(arr(i)) + 1 Next nInd = LBound(arr) For i = nMin To nMax If aTemp(i) > 0 Then For j = 1 To aTemp(i) arr(nInd) = i nInd = nInd + 1 Next End If Next Erase aTemp End Sub[/code] 如果待排序数据为正整数,将其按位数由后至前,按各位数进行排序,直至结束。 如数列:210, 35, 125, 8, 57, 63, 20, 38 第一次排序个位数,得:21 0, 02 0, 06 3, 03 5, 12 5, 05 7, 00 8, 03 8第二次排序十位数,得:0 08, 2 10, 0 20, 1 25, 0 35, 0 38, 0 57, 0 63 第三次排序百位数,得: 008, 020, 035, 038, 057, 063, 125, 210 上述这样由后至前的排序方式称为最小显著数字基数排序(Least Significant Digit),如果是由前向后则被称为最大显著数字基数排序(Most Significant Digit)。前者适合整数的排序,后者适合字符串的排序。 如果我们进一步观察上述步骤,第一次排序是对 元素 对于 10 的余数排序,而第二次则是 INT(元素/10) 对于 10 的余数排序,第三次是 INT(元素/100) 对于 10 的余数排序,即由10 ^ 0 次方开始向上增长,基数为10。这也是其被称为基数排序的原因。更为普遍的,我们可以对一个正整数序列使用任意的基数进行排序。 以下代码是一个对正整数数列的基数排序,基数可以是任何大于1的数值。 [code=vb]Sub RadixSort(ByRef aData&(), ByVal nRadix&) Dim i&, aBucket&(), arr, nMaxNum&, nExp&, k%, nLB&, nUB& nLB = LBound(aData): nUB = UBound(aData) For i = nLB To nUB If aData(i) > nMaxNum Then nMaxNum = aData(i) Next ReDim arr(nLB To nUB) nExp = 1 Do ReDim aBucket(0 To nRadix - 1) For i = nLB To nUB k = Int(aData(i) / nExp) Mod nRadix aBucket(k) = aBucket(k) + 1 Next For i = 1 To nRadix - 1 aBucket(i) = aBucket(i) + aBucket(i - 1) Next For i = nUB To nLB Step -1 k = Int(aData(i) / nExp) Mod nRadix arr(aBucket(k) + nLB - 1) = aData(i) aBucket(k) = aBucket(k) - 1 Next aData = arr nExp = nExp * nRadix If nMaxNum / nExp < 1 Then Exit Do Loop End Sub[/code]
到此先告一段落,基本的排序方法介绍完了,有机会再加~ |