ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

   
EH云课堂-专业的职场技能充电站 Excel转在线管理系统,怎么做看这里 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
Excel不给力? 何不试试FoxTable! Excel 2016函数公式学习大典 高效办公必会的Office实战技巧 免费下载Excel行业应用视频
300集Office 2010微视频教程 Tableau-数据可视化工具 精品推荐-800套精选PPT模板,点击获取 ExcelHome出品 - VBA代码宝免费下载
你的Excel 2010实战技巧学习锦囊 欲罢不能, 过目难忘的 Office 新界面 Excel VBA经典代码实践指南
查看: 47868|回复: 153
打印 上一主题 下一主题

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

  [复制链接]

ag娱乐平台手机版,  埃斯拉姆伯基试图将AT&T数以百计的计算机系统进行合并。随着更多的电话和数据流量通过基于IP协议的高速线路进行传输,因而对多系统的需求也正在减少。由于减少了网络系统数量,AT&T就可以削减员工数量。

  黄渤说不知道,嘉宾解释道:“马云说,‘男人的长相和他的才华往往是成反比的’,我不知道黄渤你怎么看这句话呢?“。黄渤不紧不慢地回击:“我相信这话也一直激励着您。”吴柳莹撰文支持羽球联赛 推广羽球增加球员收入  雪白的双腿交叠错落、微斜的身体微微颤动,双腿交叠、微斜身体看似优雅,端庄,其实是女人的一种身体的暗示。双腿交叠时会使腿部更加紧绷,臀部更加圆滑,那是对可能发生的行为做出的某种准备,更会让人联想到这是紧张投入而呈现出的血脉贲张的状态。

ag娱乐平台手机版TA的精华主题

TA的得分主题

跳转到指定楼层
1
发表于 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):
往后翻,一页页看,后面会更好~

评分

参与人数 15鲜花 +31 收起 理由
复道加餐 + 1 优秀作品
lover2008 + 2
drdree + 2 优秀作品
fyure + 2 感谢帮助
18977971085 + 2

查看全部评分

TA的精华主题

TA的得分主题

2
 楼主| 发表于 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的得分主题

3
 楼主| 发表于 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)使用不同方法排序的可视化图。




点评

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

评分

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

查看全部评分

TA的精华主题

TA的得分主题

4
 楼主| 发表于 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]


下图为由下至上的合并算法可视化图:



TA的精华主题

TA的得分主题

5
 楼主| 发表于 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排序的可视化图:


  • 快速排序


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

快速排序的可视化图:

ag娱乐平台手机版TA的精华主题

TA的得分主题

6
 楼主| 发表于 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]


希尔排序的可视化图:


最初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的得分主题

7
 楼主| 发表于 2013-4-20 14:58 | 只看该作者
本帖最后由 lee1892 于 2013-4-20 16:22 编辑

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

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

  • 关于合并排序
    合并排序也是基于分治思路的一种排序算法。它是唯一的具有O(n log n)最差时间复杂度的稳定的排序算法。由于其采用了明确的分治方法,合并排序可以非常容易的实现并行计算,对于多核心或多CPU的系统而言,并行计算能够极大的加快执行速度,其并行设计可既应用在由上至下的分区阶段,也可同时应用在合并阶段。另外,合并排序通常是对链表排序的最佳选择,相较而言,快速排序应用在链表上表现非常差,而堆排序则几乎无法实现。合并排序也被广泛用于慢介质存储器上。
  • 关于堆排序
    堆排序作为具有O(n log n)最差时间复杂度的排序算法也被广泛应用,它不像快速排序有退化至O(n ^ 2)的可能。内省排序(Introsort)就是结合使用了快速排序和堆排序来实现的,这种结合不同排序算法的实现就被称为混合排序。
  • 关于快速排序
    快速排序有着最佳的平均时间复杂度,对于一个乱序数据而言,是最佳的选择。但快速排序有退化至O(n ^ 2)的可能,使得其存在安全上的风险。另外,快速排序使用了递归,可能会大量占用递归堆栈空间,甚至造成溢出。在实际使用中,通常都会对快速排序作优化:结合其它排序算法(如在数据数量小于一定个数时,直接采用插入排序)、选择合适的基准值(如随机选择)、采用3分区法(3-Way Quick Sort)等。当前大多数流行的程序语言中都有内置的Sort方法,通常都是使用的快速排序法的优化。
  • 关于希尔排序
    希尔排序虽然在较小的数据量时有着较快的速度,但在实际应用中却很少使用。偶尔被一些混合排序算法使用在较小数据数量情况下,作为避免及减少递归次数。

对一个排序算法的评价,除了上述的时间、空间复杂度以及稳定性等因素外,还要考量其对不同特征的源数据的排序效果。通常这样的考量针对情况是:乱序、已基本排序、完全倒序、有很多重复值等情况。参考网站:/www133bsorting-algorithms133bcom

单纯的评价某个排序算法最佳从来都不是一个明智的事情。

楼上的点评还真敢写~~居然还冒出个彭氏算法,Sigh~~~




点评

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

TA的精华主题

TA的得分主题

8
 楼主| 发表于 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的得分主题

9
 楼主| 发表于 2013-4-20 16:27 | ag娱乐平台手机版只看该作者
到此先告一段落,基本的排序方法介绍完了,有机会再加~

TA的精华主题

TA的得分主题

10
发表于 2013-4-20 17:51 | 只看该作者
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

关闭

最新热点上一条 /1 下一条

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

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

GMT+8, 2019-6-19 03:23 , Processed in 0.122088 second(s), 13 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 2001-2017 Wooffice Inc.

   

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

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

快速回复 ag娱乐平台手机版 返回列表
巴以冲突被指“屠杀” 美却称联合国调查无耻(图) 猖狂 男子当着母亲面将12岁少女拖进消防通道猥亵 89岁老人孤苦无依?发布团队道歉:不客观(图) 卖了超市再卖百货:韩国乐天集团正全面撤出中国市场 中方迟迟没有答复澳外长访华请求?外交部回应 曾莫哲:黄金暗有所指 就等包威尔一锤定音 北京雪难进城区 今起回暖最高升至15℃昼夜温差大 台当局统计:3月台湾对大陆出口额创历年单月新高 高管出走:特斯拉更难留住股票短期卖空者 人民日报:有些干部把为官平庸视为“超脱” 民航局调查组正深入调查川航备降事件 法方参与 格德斯:听说要对中超裁判客气点 首要目标拿冠军
14部委严打:比特币开年遭腰斩 区块链池鱼之祸 俄罗斯研制新型无人歼击机应对微型无人机 中国2款四代机将亮相珠海航展 20系列飞机或集体登场 人民日报:文化交流要增强主体意识 纳达尔谈和莎娃罗马训练:感觉很棒 强度很大 韩推“手机僵尸”APP治低头族 走路时手机自动锁屏 日本万吨神盾大驱下水 与参加过淞沪会战旧舰同名 农工党中央:增加对二孩家庭税收激励 可对其退税 辽媒:没伤病北京是前四的实力 辽篮别想着横扫 全国人大相关负责人:让人大监督“牙齿”越来越硬 辽宁舰航母编队完成训练返港:锻炼提升体系作战能力 苏皇银行与美国政府达成和解 认罚49亿美元
中国人在澳被指存在感日增:“定制”服务应运而生 曝皇马新帅重点特训贝尔:新赛季靠你顶替C罗啦 肯尼亚医生搞错病人身份牌 给无需手术者开颅 美墨加谈判收效甚微 NAFTA协定能否快速达成遭疑 扎克伯格今天34岁:出生以来平均每天赚600万美元 女用户占比41.4% 保护乘客人身安全滴滴还任重道远 家长为孩子报“蒙眼识字”培训班 却是教斜眼偷看 连续四年提交AI提案 李彦宏称AI中美竞赛优势在数据 政协发言人王国庆这三年:共回答中外媒体51个问题 人类首次发现银河系外行星 距离地球38亿光年 特蕾莎·梅后院起火 英国脱欧现实引发保守党内战 孔蒂:我愿意和切尔西续约 希望俱乐部公开支持我 亚股创2016年底来最大日内跌幅 美股重跌全球不安 ag娱乐平台手机版