ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

   
EH云课堂-专业的职场技能充电站 永久免费,网表让Excel秒变数据库 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
Excel不给力? 何不试试FoxTable! Excel函数公式学习大典 高效办公必会的Office实战技巧 免费下载Excel行业应用视频
300集Office 2010微视频教程 Tableau-数据可视化工具 ExcelHome出品 - VBA代码宝免费下载 13门Excel免费公开课任你学
你的Excel 2010实战技巧学习锦囊 欲罢不能, 过目难忘的 Office 新界面 免费的Excel考勤计算系统
查看: 42097|回复: 144

[原创] VBA编程技巧 之 排序算法初探

  [复制链接]

TA的精华主题

TA的得分主题

发表于 2013-4-16 14:02 | 显示全部楼层 |阅读模式
本帖已被收录到知识树中,索引项:排序
本帖最后由 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)
...
其它 ...









补充内容 (2013-4-26 09:33):
往后翻,一页页看,后面会更好~

评分

参与人数 13鲜花 +28 收起 理由
drdree + 2 优秀作品
fyure + 2 感谢帮助
18977971085 + 2
weisilisid + 2 优秀作品
annamissu + 2 感谢帮助,我正在写个排序代码作为练习,但.

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-4-17 09:37 | 显示全部楼层
本帖最后由 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!) 阶乘(阶)


点评

请大家暂时不要跟帖、回帖哦! 让楼主轻松占楼。  发表于 2013-4-17 11:20

TA的精华主题

TA的得分主题

发表于 2013-4-17 10:43 | 显示全部楼层

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-4-18 12:28 | 显示全部楼层
本帖最后由 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)使用不同方法排序的可视化图。
01.双循环对比排序.PNG
02.冒泡排序.PNG
03.选择排序.PNG
04.插入排序.PNG

点评

这个图表做的非常有意思……直观地显示出各种排序的差别。  发表于 2013-4-20 22:27

评分

参与人数 1鲜花 +3 收起 理由
hhjjpp + 3 复习多年前的冒泡算法

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-4-19 14:33 | 显示全部楼层
本帖最后由 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]


下图为由下至上的合并算法可视化图:
05.合并排序.PNG

05.合并排序_示意.PNG

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-4-20 11:50 | 显示全部楼层
  • 堆排序


运作方式:
顾名思义,所谓堆排序是利用堆这个数据结构来进行排序。我们知道堆顶是堆中数据的最值元素,那么不断的从堆顶提出元素并顺序的放置数据中就可以得到一个有序数据。最为常用的是二叉堆排序。关于堆的讨论,可参考我的数据结构的帖子。

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排序的可视化图:
06.堆排序.PNG

  • 快速排序


运作方式:
快速排序与二叉查找树基于一样的思路,采用了分治(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]

快速排序的可视化图:
07.快速排序.PNG

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-4-20 13:42 | 显示全部楼层
本帖最后由 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]


希尔排序的可视化图:
08.希尔排序.PNG

最初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, ... 未知 在大数组中有优异表现

值得指出的是,希尔排序通常只在数量较小的数组中表现较好,但通常的对于大量数据而言希尔排序比快速排序慢。



点评

灰袍法师也弄了个希尔排序序列的说。  发表于 2013-4-20 22:32
前几年彭希仁版主发表过彭氏算法,速度相当惊人,但用直接填充数组在数据位数不超过5位的情况下好象比彭氏算法要快。几年前我作过比较。  发表于 2013-4-20 14:06
如果数据特殊(全部为整数),直接填充数组 dim arr(最小值 to 最大值, 1 to 2) ,再整理数组,速度也是相当惊人的。Arr(i,1)填数,Arr(i,2)填重复数。  发表于 2013-4-20 13:49

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-4-20 14:58 | 显示全部楼层
本帖最后由 lee1892 于 2013-4-20 16:22 编辑

基于比较的排序算法的小结

以上排序算法的附件: 排序算法初探_By Lee1892.rar (30.72 KB, 下载次数: 453)

点评

参考网站全英文,看不懂!!  发表于 2013-4-26 17:17

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-4-20 16:09 | 显示全部楼层
本帖最后由 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
第一次排序个位数,得:210, 020, 063, 035, 125, 057, 008, 038
第二次排序十位数,得:008, 210, 020, 125, 035, 038, 057, 063
第三次排序百位数,得: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]

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-4-20 16:27 | 显示全部楼层
到此先告一段落,基本的排序方法介绍完了,有机会再加~
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

关注官方微信,高效办公专列,每天发车

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2018-12-17 08:42 , Processed in 0.155141 second(s), 20 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 2001-2017 Wooffice Inc.

   

沪公网安备 31011702000001号 沪ICP备11019229号

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:徐怀玉律师 李志群律师

快速回复 返回顶部 返回列表