ExcelHome技术论坛

标题: VBA编程技巧 之 排序算法初探 [打印本页]

作者: lee1892    时间: 2013-4-16 14:02
标题: VBA编程技巧 之 排序算法初探
本帖最后由 lee1892 于 2013-4-17 09:45 编辑

一些说明

由于论坛设置了编辑帖子的时限,而我写帖子喜欢不断加新内容,所以这个帖子就不再设顶楼目录了。

另外,这个帖子内容会比较多,所以我估计发帖的时间跨度会比较大。考虑到期间别人的回帖,那么我发的帖子会比较分散,建议看贴的时候可以点击 只看该作者

前言

顾名思义,所谓排序算法(Sorting Algorithm)就是将一组数据按某种特定的顺序重新排列组织。显然,这一需要是我们在日常处理工作当中总是要用到的。这也是排序算法是计算机世界中最为重要的算法的原因。最为常见的顺序是 数值顺序 和 字符顺序。对于一些其它算法的优化,一个高效的排序算法是起决定性作用的,比如查找、合并等。

排序算法的分类与评价


排序方式 排序算法
交换排序(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):
往后翻,一页页看,后面会更好~
作者: lee1892    时间: 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!) 阶乘(阶)



作者: lee1892    时间: 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)使用不同方法排序的可视化图。
(, 下载次数: 393)
(, 下载次数: 377)
(, 下载次数: 510)
(, 下载次数: 426)

作者: lee1892    时间: 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]


下图为由下至上的合并算法可视化图:
(, 下载次数: 394)

(, 下载次数: 407)

作者: lee1892    时间: 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排序的可视化图:
(, 下载次数: 414)



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

快速排序的可视化图:
(, 下载次数: 329)

作者: lee1892    时间: 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]


希尔排序的可视化图:
(, 下载次数: 353)

最初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 14:58
本帖最后由 lee1892 于 2013-4-20 16:22 编辑

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

以上排序算法的附件: (, 下载次数: 842)


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

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

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





作者: lee1892    时间: 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]

作者: lee1892    时间: 2013-4-20 16:27
到此先告一段落,基本的排序方法介绍完了,有机会再加~
作者: yjh_27    时间: 2013-4-20 17:51
留个记号,慢慢学。
作者: bluexuemei    时间: 2013-4-20 21:40
太牛了,下载后慢慢消化。
作者: 香川群子    时间: 2013-4-20 22:36
一般我就用选择排序……或者偷懒直接输出结果到工作表后排序。
作者: hehex    时间: 2013-4-22 13:59
好东西啊,需要慢慢消化。不太会C 语言,研究算法特别是指针的地方费劲了哦。
谢谢lee1892 大师
作者: wuxinyun1999    时间: 2013-4-22 16:03
看的眼花缭乱啊,膜拜一下。
等进化了再来消化,楼主辛苦了。
作者: Moneky    时间: 2013-4-22 18:51
多谢楼主辛苦分享,收藏待查。。。。。。
作者: fycrik    时间: 2013-4-22 19:34
表示太高深了 膜拜一下 以后再看
作者: coverne    时间: 2013-4-23 11:34
严重关注,茅塞顿开
作者: gjj136138139    时间: 2013-4-23 12:57
相当牛,只会工作表排序法。
作者: lee1892    时间: 2013-4-24 12:28
希尔排序算法中不同步长序列的速度测试

下述代码测试了不同步长序列的执行速度,参考会跑法师的  有史以来最快的希尔排序
代码:
Sub TestShellSpeed()
    Dim i&, t#, aData!(), arr, j&, sMsg$, aGaps
    ReDim aData(1 To 1500)
    Randomize
    For i = 1 To UBound(aData)
        aData(i) = Rnd
    Next
    Debug.Print
    For i = 0 To 5
        Select Case i
        Case 0
            aGaps = Array(929, 503, 211, 109, 41, 19, 5, 1)
            sMsg = "法师改良的 Sedgewick 奇偶 序列"
        Case 1
            aGaps = Array(929, 505, 209, 109, 41, 19, 5, 1)
            sMsg = "原本的 Sedgewick 奇偶 序列"
        Case 2
            aGaps = Array(1073, 281, 77, 23, 8, 1)
            sMsg = "Sedgewick 的 序列"
        Case 3
            aGaps = Array(1182, 525, 233, 103, 46, 20, 9, 4, 1)
            sMsg = "Tokuda 的 序列"
        Case 4
            aGaps = Array(701, 301, 132, 57, 23, 10, 4, 1)
            sMsg = "Ciura 的 序列"
        Case 5
            aGaps = Array(836, 182, 34, 9, 1)
            sMsg = "基于费波那契数列的 序列"
        End Select
        t = Timer
        For j = 1 To 10 ^ 2 * 2
            arr = aData
            Call ShellSort(arr, aGaps)
        Next
        Debug.Print sMsg & ":" & Join(aGaps, ", ")
        Debug.Print Format(Timer - t, "0.000 秒")
    Next
End Sub

Sub ShellSort(ByRef arr, ByRef aGaps)
    Dim i&, j&, vTemp, nGap, nLen&
    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) = vTemp
        Next
    Next
End Sub


我测试了5次所获结果如下:
  1. 法师改良的 Sedgewick 奇偶 序列:929, 503, 211, 109, 41, 19, 5, 1
  2. 1.328 秒
  3. 原本的 Sedgewick 奇偶 序列:929, 505, 209, 109, 41, 19, 5, 1
  4. 1.324 秒
  5. Sedgewick 的 序列:1073, 281, 77, 23, 8, 1
  6. 1.438 秒
  7. Tokuda 的 序列:1182, 525, 233, 103, 46, 20, 9, 4, 1
  8. 1.313 秒
  9. Ciura 的 序列:701, 301, 132, 57, 23, 10, 4, 1
  10. 1.297 秒
  11. 基于费波那契数列的 序列:836, 182, 34, 9, 1
  12. 1.621 秒

  13. 法师改良的 Sedgewick 奇偶 序列:929, 503, 211, 109, 41, 19, 5, 1
  14. 1.355 秒
  15. 原本的 Sedgewick 奇偶 序列:929, 505, 209, 109, 41, 19, 5, 1
  16. 1.391 秒
  17. Sedgewick 的 序列:1073, 281, 77, 23, 8, 1
  18. 1.406 秒
  19. Tokuda 的 序列:1182, 525, 233, 103, 46, 20, 9, 4, 1
  20. 1.297 秒
  21. Ciura 的 序列:701, 301, 132, 57, 23, 10, 4, 1
  22. 1.281 秒
  23. 基于费波那契数列的 序列:836, 182, 34, 9, 1
  24. 1.480 秒

  25. 法师改良的 Sedgewick 奇偶 序列:929, 503, 211, 109, 41, 19, 5, 1
  26. 1.313 秒
  27. 原本的 Sedgewick 奇偶 序列:929, 505, 209, 109, 41, 19, 5, 1
  28. 1.309 秒
  29. Sedgewick 的 序列:1073, 281, 77, 23, 8, 1
  30. 1.391 秒
  31. Tokuda 的 序列:1182, 525, 233, 103, 46, 20, 9, 4, 1
  32. 1.281 秒
  33. Ciura 的 序列:701, 301, 132, 57, 23, 10, 4, 1
  34. 1.297 秒
  35. 基于费波那契数列的 序列:836, 182, 34, 9, 1
  36. 1.500 秒

  37. 法师改良的 Sedgewick 奇偶 序列:929, 503, 211, 109, 41, 19, 5, 1
  38. 1.313 秒
  39. 原本的 Sedgewick 奇偶 序列:929, 505, 209, 109, 41, 19, 5, 1
  40. 1.309 秒
  41. Sedgewick 的 序列:1073, 281, 77, 23, 8, 1
  42. 1.422 秒
  43. Tokuda 的 序列:1182, 525, 233, 103, 46, 20, 9, 4, 1
  44. 1.281 秒
  45. Ciura 的 序列:701, 301, 132, 57, 23, 10, 4, 1
  46. 1.266 秒
  47. 基于费波那契数列的 序列:836, 182, 34, 9, 1
  48. 1.543 秒

  49. 法师改良的 Sedgewick 奇偶 序列:929, 503, 211, 109, 41, 19, 5, 1
  50. 1.340 秒
  51. 原本的 Sedgewick 奇偶 序列:929, 505, 209, 109, 41, 19, 5, 1
  52. 1.313 秒
  53. Sedgewick 的 序列:1073, 281, 77, 23, 8, 1
  54. 1.406 秒
  55. Tokuda 的 序列:1182, 525, 233, 103, 46, 20, 9, 4, 1
  56. 1.297 秒
  57. Ciura 的 序列:701, 301, 132, 57, 23, 10, 4, 1
  58. 1.277 秒
  59. 基于费波那契数列的 序列:836, 182, 34, 9, 1
  60. 1.531 秒
复制代码
显然,我个人认为法师所谓的改良是很没有道理的~~

作者: liucqa    时间: 2013-4-24 12:33
本帖最后由 liucqa 于 2013-4-24 12:43 编辑
lee1892 发表于 2013-4-24 12:28
希尔排序算法中不同步长序列的速度测试

下述代码测试了不同步长序列的执行速度,参考会跑法师的  有史以 ...

搞100万数据测试看看


法师改良的 Sedgewick 奇偶 序列:929, 503, 211, 109, 41, 19, 5, 1
1.152 秒
原本的 Sedgewick 奇偶 序列:929, 505, 209, 109, 41, 19, 5, 1
1.152 秒
Sedgewick 的 序列:1073, 281, 77, 23, 8, 1
1.270 秒
Tokuda 的 序列:1182, 525, 233, 103, 46, 20, 9, 4, 1
1.164 秒
Ciura 的 序列:701, 301, 132, 57, 23, 10, 4, 1
1.180 秒
基于费波那契数列的 序列:836, 182, 34, 9, 1
1.363 秒

作者: lee1892    时间: 2013-4-24 12:49
liucqa 发表于 2013-4-24 12:33
搞100万数据测试看看

100万干嘛用希尔?基于快速排序的改良和混合要好的多。
再大的,超过内存限制的,只能用合并~
作者: liucqa    时间: 2013-4-24 14:04
lee1892 发表于 2013-4-24 12:49
100万干嘛用希尔?基于快速排序的改良和混合要好的多。
再大的,超过内存限制的,只能用合并~

就VBA而言,由于在Excel中使用,最大的数据量是100万,所以给出一个支持100万数据的排序算法还是很有意义的。

我试过法师的排序,1000万 long型随机数据与标准的Sedgewick序列相比,大约快了2~3秒。100万long型随机数据大约快0.1~0.15左右,也许对普通用户来说用哪个序列都无所谓的吧。

你有空可以测试一下。

当然,如果你能给出一个快速排序+希尔排序的混合算法,或者快速排序和其他排序的混合算法也可以,只要能保证堆栈不会溢出就行。

具体多大的数据量会导致快速排序的堆栈溢出,我没有做过测试,希望你有空能测一下,谢谢!



作者: liucqa    时间: 2013-4-24 14:12
本帖最后由 liucqa 于 2013-4-24 15:24 编辑

排序演示:

插入排序演示过程:http://student.zjzk.cn/course_wa ... html/insertsort.htm
直接选择排序演示过程::http://student.zjzk.cn/course_wa ... ml/zhijiexuanze.htm
冒泡排序演示过程::http://student.zjzk.cn/course_wa ... tml/maopaopaixu.htm
快速排序演示过程::http://student.zjzk.cn/course_wa ... tml/kuaisupaixu.htm
堆排序演示过程::http://student.zjzk.cn/course_wa ... shhtml/duipaixu.htm
基数排序演示过程::http://student.zjzk.cn/course_wa ... html/jishupaixu.htm
桶排序演示过程::http://student.zjzk.cn/course_wa ... hhtml/tongpaixu.htm
归并排序演示过程::http://student.zjzk.cn/course_wa ... ml/guibingpaixu.htm

排序大比武
http://www.cppblog.com/Chipset/archive/2011/08/16/153559.html

不懂排序的人,没事可以看看


作者: lee1892    时间: 2013-4-24 15:50
本帖最后由 lee1892 于 2013-4-24 15:54 编辑
liucqa 发表于 2013-4-24 14:04
就VBA而言,由于在Excel中使用,最大的数据量是100万,所以给出一个支持100万数据的排序算法还是很有意义 ...

对于快速排序而言,数据量的大小并不会是导致堆栈溢出的主要原因,而是数据是否是精心设计过的。

而所谓精心设计,是指对某种基准值选择方法而特定设计的数据顺序,通常是针对较普遍的基准值选择的几种方法:选第一个元素、选最后一个元素、选第一个和最后一个以及中间一个这三者中的中间值、随机选择(先随机的将一个元素与第一个元素对调),等。

实际上,一个乱序数组是不太可能造成堆栈溢出的,比如在我的机器上单精度数组最大可申请到10^7 ~ 10^8 之间,如果你愿意的话,可以反复测试下述代码是否会堆栈溢出,呵呵:
说实在的,我很怀疑坛子里有几个人能设计出这样的顺序,嘿嘿~
代码:
Sub TestQuickSortSpeed()
    Dim i&, t#, aData!(), arr, nLen&
    nLen = 10 ^ 7
    ReDim aData(1 To nLen)
    Randomize
    For i = 1 To UBound(aData)
        aData(i) = Rnd
    Next
    Debug.Print
    t = Timer
    arr = aData
    Call QuickSort(arr, 1, nLen)
    Debug.Print "原始的快速排序:"
    Debug.Print Format(Timer - t, "0.000 秒")
End Sub
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


作者: lee1892    时间: 2013-4-24 16:26
liucqa 发表于 2013-4-24 14:12
排序演示:

插入排序演示过程:http://student.zjzk.cn/course_wa ... html/insertsort.htm

http://www.cppblog.com/Chipset/
的博客里看到最可乐的Bogo排序算法:
  1. while (没有排好序)
  2. 打乱当前序列的顺序;
复制代码
LOL~~~
作者: liucqa    时间: 2013-4-25 00:24
本帖最后由 liucqa 于 2013-4-25 00:31 编辑

http://www.doc88.com/p-905591811549.html
有空测试一下这个论文的真假



这有个快速排序比较全的
http://www.cnblogs.com/mfryf/archive/2012/08/06/2625300.html

作者: lee1892    时间: 2013-4-25 00:36
liucqa 发表于 2013-4-25 00:24
http://www.doc88.com/p-905591811549.html
有空测试一下这个论文的真假

我建议搞定IntroSort和TimSort,在合适的地方选择结合分配排序加速第一步工作,就完全OK了。

最多练一下上述两个混合排序,结合合并排序,以应付超大规模的数据,必须要用文件作为介质的情况。

当然兴趣所在就是另一回事了{:soso_e113:}

作者: lee1892    时间: 2013-4-25 12:08
本帖最后由 lee1892 于 2013-4-25 13:39 编辑
liucqa 发表于 2013-4-24 12:33
搞100万数据测试看看

关于希尔排序不同的步长序列的选择,仅仅考查用时似乎并不是完整的工作

下述代码,在前述基础上:
1、增加了Gonnet & Baeza-Yates于1991年发布的序列
2、对于Ciura,这个是迄今最快的序列,但701以上部分则还处于未知状态,这里用 h(k) = INT(2.25*h(k-1))进行扩展
3、统计了元素移动的次数,以及元素间对比的次数,并分别计算了时间复杂度的增长阶

可以看到,法师改良的前后互质的Sedgewick双公式序列,速度确实快,但移动和对比的次数仍较Ciura序列多。

代码:
Sub TestShellSpeed()
    Dim i&, t#, aData!(), arr, j&, sMsg$, aGaps, nLen&
    Dim nMov As Currency, nCom As Currency
    nLen = 10 ^ 5 * 3 ' <-- 数据数量
    ReDim aData(1 To nLen)
    Randomize
    For i = 1 To UBound(aData)
        aData(i) = Rnd
    Next
    Debug.Print
    Debug.Print "希尔排序中不同步长序列的对比:"
    Debug.Print "随机单精度数据数量:" & Format(nLen, "#,##")
    For i = 0 To 6
        Call GetShellGaps(aGaps, nLen, i, sMsg)
        t = Timer
        arr = aData
        Call ShellSort(arr, aGaps, nMov, nCom)
        Debug.Print sMsg & ":" & Join(aGaps, ", ")
        Debug.Print Format(Timer - t, "用时 0.000 秒"), _
                    Format(nMov, "移动 #,##") & " / N ^ " & Format(Log(nMov) / Log(nLen), "0.000"), _
                    Format(nCom, "比较 #,##") & " / N ^ " & Format(Log(nCom) / Log(nLen), "0.000")
    Next
End Sub

Sub ShellSort(ByRef arr, ByRef aGaps, _
              Optional ByRef nMove As Currency, _
              Optional ByRef nCompare As Currency)
    Dim i&, j&, vTemp, nGap, nLen&
    nLen = UBound(arr)
    nMove = 0: nCompare = 0
    For Each nGap In aGaps
        For i = nGap + 1 To nLen
            vTemp = arr(i)
            For j = i To nGap + 1 Step nGap * -1
                nCompare = nCompare + 1
                If arr(j - nGap) < vTemp Then Exit For
                arr(j) = arr(j - nGap)
                nMove = nMove + 1
            Next
            arr(j) = vTemp: nMove = nMove + 1
        Next
    Next
End Sub

Sub GetShellGaps(ByRef arrGaps As Variant, _
                 ByVal nArrLen As Currency, _
                 Optional ByVal nGapType As Integer = 0, _
                 Optional ByRef sMessage As String = "")
    Dim i&, nNum&, aTemp, nCount&
    Select Case nGapType
    Case 0 ' Ciura\2001
        sMessage = "Ciura 的 序列"
        aTemp = Array(1, 4, 10, 23, 57, 132, 301, 701, 1750) ' 按原论文增加1750
        If nArrLen < 2.25 * aTemp(UBound(aTemp)) Then
            For nNum = UBound(aTemp) To 0 Step -1
                If aTemp(nNum) < nArrLen Then Exit For
            Next
        Else
            nNum = UBound(aTemp)
            Do
                nNum = nNum + 1
                If UBound(aTemp) < nNum Then ReDim Preserve aTemp(0 To nNum + 10)
                aTemp(nNum) = Int(aTemp(nNum - 1) * 2.25)
                If aTemp(nNum) > nArrLen Then nNum = nNum - 1: Exit Do
            Loop
        End If
    Case 1 ' Tokuda\1992
        sMessage = "Tokuda 的 序列"
        ReDim aTemp(0 To 10)
        nNum = 0
        Do
            aTemp(nNum) = Int((9 ^ (nNum + 1) - 4 ^ (nNum + 1)) / (5 * 4 ^ nNum)) + IIf(nNum, 1, 0)
            If aTemp(nNum) > nArrLen Then nNum = nNum - 1: Exit Do
            nNum = nNum + 1
            If UBound(aTemp) < nNum Then ReDim Preserve aTemp(0 To nNum + 10)
        Loop
    Case 2 ' Gonnet & Baeza-Yates\1991
        sMessage = "Gonnet & Baeza-Yates 的 序列"
        ReDim aTemp(0 To 10)
        nNum = 0: aTemp(nNum) = Int(5 * nArrLen / 11)
        Do
            If aTemp(nNum) <= 1 Then
                aTemp(nNum) = 1
                ReDim Preserve aTemp(0 To nNum)
                arrGaps = aTemp
                Exit Sub
            End If
            nNum = nNum + 1
            If UBound(aTemp) < nNum Then ReDim Preserve aTemp(0 To nNum + 10)
            aTemp(nNum) = Int(5 * aTemp(nNum - 1) / 11)
        Loop
    Case 3 ' Sedgewick\1986 双公式
        sMessage = "原本的 Sedgewick 双公式 序列"
        ReDim aTemp(0 To 10)
        nNum = 0: nCount = 1
        Do
            aTemp(nNum) = 9 * (4 ^ (nCount - 1) - 2 ^ (nCount - 1)) + 1
            If aTemp(nNum) > nArrLen Then nNum = nNum - 1: Exit Do
            nNum = nNum + 1
            If UBound(aTemp) < nNum Then ReDim Preserve aTemp(0 To nNum + 10)
            aTemp(nNum) = 4 ^ (nCount + 1) - 6 * 2 ^ nCount + 1
            If aTemp(nNum) > nArrLen Then nNum = nNum - 1: Exit Do
            nNum = nNum + 1
            If UBound(aTemp) < nNum Then ReDim Preserve aTemp(0 To nNum + 10)
            nCount = nCount + 1
        Loop
    Case 4 ' Sedgewick\1986 单公式
        sMessage = "Sedgewick 单公式 序列"
        ReDim aTemp(0 To 10)
        aTemp(0) = 1: nNum = 1
        Do
            aTemp(nNum) = 4 ^ nNum + 3 * 2 ^ (nNum - 1) + 1
            If aTemp(nNum) > nArrLen Then nNum = nNum - 1: Exit Do
            nNum = nNum + 1
            If UBound(aTemp) < nNum Then ReDim Preserve aTemp(0 To nNum + 10)
        Loop
    Case 5 ' 基于 Fibonacci
        sMessage = "基于费波那契数列的 序列"
        aTemp = Array(1, 9, 34, 182, 835, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713, 2147483647)
        For nNum = UBound(aTemp) To 0 Step -1
            If aTemp(nNum) < nArrLen Then Exit For
        Next
    Case 6 ' Sedgewick\1986 双公式 法师改良 前后互质
        sMessage = "法师改良 前后互质的 Sedgewick 双公式 序列"
        aTemp = Array(1, 5, 19, 41, 109, 211, 503, 929, 2161, 3907, 8929, 16001, 36293, 64763, 146309, 260609, 587527, 1045055, 2354689, 4188161, 9427969)
        For nNum = UBound(aTemp) To 0 Step -1
            If aTemp(nNum) < nArrLen Then Exit For
        Next
    End Select
    ReDim arrGaps(0 To nNum)
    For i = 0 To nNum
        arrGaps(i) = aTemp(nNum - i)
    Next
End Sub



作者: lee1892    时间: 2013-4-25 12:13
30万和100万两次运行的结果:


希尔排序中不同步长序列的对比:
随机单精度数据数量:300,000
Ciura 的 序列:204585, 90927, 40412, 17961, 7983, 3548, 1577, 701, 301, 132, 57, 23, 10, 4, 1
用时 3.156 秒 移动 8,717,408 / N ^ 1.267  比较 8,576,205 / N ^ 1.266
Tokuda 的 序列:153401, 68178, 30301, 13467, 5985, 2660, 1182, 525, 233, 103, 46, 20, 9, 4, 1
用时 3.406 秒 移动 8,774,041 / N ^ 1.268  比较 8,616,856 / N ^ 1.266
Gonnet & Baeza-Yates 的 序列:136363, 61983, 28174, 12806, 5820, 2645, 1202, 546, 248, 112, 50, 22, 10, 4, 1
用时 4.293 秒 移动 11,652,160 / N ^ 1.290 比较 11,501,987 / N ^ 1.289
原本的 Sedgewick 双公式 序列:260609, 146305, 64769, 36289, 16001, 8929, 3905, 2161, 929, 505, 209, 109, 41, 19, 5, 1
用时 3.516 秒 移动 8,942,928 / N ^ 1.269  比较 8,785,233 / N ^ 1.268
Sedgewick 单公式 序列:262913, 65921, 16577, 4193, 1073, 281, 77, 23, 8, 1
用时 3.934 秒 移动 10,718,795 / N ^ 1.284 比较 10,613,008 / N ^ 1.283
基于费波那契数列的 序列:90358, 19001, 4025, 835, 182, 34, 9, 1
用时 4.500 秒 移动 13,550,891 / N ^ 1.302 比较 13,438,342 / N ^ 1.301
法师改良 前后互质的 Sedgewick 双公式 序列:260609, 146309, 64763, 36293, 16001, 8929, 3907, 2161, 929, 503, 211, 109, 41, 19, 5, 1
用时 3.109 秒 移动 8,929,300 / N ^ 1.269  比较 8,771,494 / N ^ 1.268

希尔排序中不同步长序列的对比:
随机单精度数据数量:1,000,000
Ciura 的 序列:460316, 204585, 90927, 40412, 17961, 7983, 3548, 1577, 701, 301, 132, 57, 23, 10, 4, 1
用时 11.902 秒              移动 32,436,606 / N ^ 1.252 比较 31,935,447 / N ^ 1.251
Tokuda 的 序列:776591, 345152, 153401, 68178, 30301, 13467, 5985, 2660, 1182, 525, 233, 103, 46, 20, 9, 4, 1
用时 12.695 秒              移动 32,570,044 / N ^ 1.252 比较 32,098,955 / N ^ 1.251
Gonnet & Baeza-Yates 的 序列:454545, 206611, 93914, 42688, 19403, 8819, 4008, 1821, 827, 375, 170, 77, 35, 15, 6, 2, 1
用时 13.012 秒              移动 33,486,493 / N ^ 1.254 比较 32,984,329 / N ^ 1.253
原本的 Sedgewick 双公式 序列:587521, 260609, 146305, 64769, 36289, 16001, 8929, 3905, 2161, 929, 505, 209, 109, 41, 19, 5, 1
用时 12.949 秒              移动 33,259,043 / N ^ 1.254 比较 32,743,432 / N ^ 1.253
Sedgewick 单公式 序列:262913, 65921, 16577, 4193, 1073, 281, 77, 23, 8, 1
用时 14.852 秒              移动 40,763,755 / N ^ 1.268 比较 40,389,065 / N ^ 1.268
基于费波那契数列的 序列:428481, 90358, 19001, 4025, 835, 182, 34, 9, 1
用时 16.945 秒              移动 51,773,670 / N ^ 1.286 比较 51,376,900 / N ^ 1.285
法师改良 前后互质的 Sedgewick 双公式 序列:587527, 260609, 146309, 64763, 36293, 16001, 8929, 3907, 2161, 929, 503, 211, 109, 41, 19, 5, 1
用时 11.574 秒              移动 33,187,703 / N ^ 1.253 比较 32,671,580 / N ^ 1.252
作者: lee1892    时间: 2013-4-25 12:50
内省排序(IntroSort)

内省排序结合了快速排序、插入排序以及堆排序,充分利用了各自的优点,其运作方式如下:

1、对于元素数量小的源数据(比如32个元素或更少),直接使用插入排序,虽然有着O(n^2)的时间复杂度,但稳定性毋庸置疑;
2、对于更多元素数量,使用三值取中法或是九值取中法的快速排序;
3、采用原地的三分快速排序,小于基准值在左、等于基准值居中、大于基准值在右;
4、对左右两个分区递归的采用上述快速排序;
5、当递归深度大于一定数值时(比如 1.5 * log N),转为堆排序。

以上算法被采用在 Microsoft STL std::sort 中。

作者: liucqa    时间: 2013-4-25 13:15
lee1892 发表于 2013-4-25 12:08
关于希尔排序不同的步长序列的选择,仅仅考查用时似乎并不是完整的工作

下述代码,在前述基础上:

http://blog.csdn.net/hustxifangshibai/article/details/619620

/*
* Ciura 算法。发表于 2001 年。性能卓越。
*/
int shellsortCi(int p[],int n)
{
int op=0;
int h,i,j,t,temp;
int incs[18] = {
  2331004, 1036002, 460445, 204643, 90952,
  40423, 17965, 7985, 3549, 1577, 701,
  301, 132, 57, 23, 9, 4, 1
};
作者: lee1892    时间: 2013-4-25 13:25
本帖最后由 lee1892 于 2013-4-25 14:18 编辑
liucqa 发表于 2013-4-25 13:15
http://blog.csdn.net/hustxifangshibai/article/details/619620

/*

701以后都是这哥们不知道哪抄来的吧,我用的是:h(k) = INT(2.25 * h(k-1)),他这个应该是:h(k) = INT(701 * 2.25^(k-9)),一回事

http://sun.aei.polsl.pl/~mciura/publikacje/shellsort.pdf

人论文里只出现到1750哦~

好吧,我修正一下,到701后面一个是1750,但也就到此为止了~




作者: liucqa    时间: 2013-4-25 13:52
本帖最后由 liucqa 于 2013-4-25 13:54 编辑
lee1892 发表于 2013-4-25 13:25
701以后都是这哥们不知道哪抄来的吧,我用的是:h(k) = INT(2.25 * h(k-1)),他这个应该是:h(k) = INT(h ...


希尔排序中不同步长序列的对比:
随机单精度数据数量:300,000
Ciura 的 序列:204643, 90952, 40423, 17965, 7985, 3549, 1577, 701, 301, 132, 57, 23, 9, 4, 1
用时 3.258 秒 移动 8,761,525 / N ^ 1.268  比较 8,620,407 / N ^ 1.266
法师改良 前后互质的 Sedgewick 双公式 序列:260609, 146309, 64763, 36293, 16001, 8929, 3907, 2161, 929, 503, 211, 109, 41, 19, 5, 1
用时 3.293 秒 移动 8,935,513 / N ^ 1.269  比较 8,777,580 / N ^ 1.268

希尔排序中不同步长序列的对比:
随机单精度数据数量:300,000
Ciura 的 序列:204643, 90952, 40423, 17965, 7985, 3549, 1577, 701, 301, 132, 57, 23, 9, 4, 1
用时 3.465 秒 移动 8,771,917 / N ^ 1.268  比较 8,630,846 / N ^ 1.266
法师改良 前后互质的 Sedgewick 双公式 序列:260609, 146309, 64763, 36293, 16001, 8929, 3907, 2161, 929, 503, 211, 109, 41, 19, 5, 1
用时 3.539 秒 移动 8,954,461 / N ^ 1.269  比较 8,797,172 / N ^ 1.268

希尔排序中不同步长序列的对比:
随机单精度数据数量:1,000,000
Ciura 的 序列:460445, 204643, 90952, 40423, 17965, 7985, 3549, 1577, 701, 301, 132, 57, 23, 9, 4, 1
用时 12.574 秒              移动 32,509,377 / N ^ 1.252 比较 32,008,371 / N ^ 1.251
法师改良 前后互质的 Sedgewick 双公式 序列:587527, 260609, 146309, 64763, 36293, 16001, 8929, 3907, 2161, 929, 503, 211, 109, 41, 19, 5, 1
用时 13.867 秒              移动 33,172,395 / N ^ 1.253 比较 32,655,966 / N ^ 1.252

希尔排序中不同步长序列的对比:
随机单精度数据数量:2,400,000
Ciura 的 序列:2331004, 1036002, 460445, 204643, 90952, 40423, 17965, 7985, 3549, 1577, 701, 301, 132, 57, 23, 9, 4, 1
用时 32.852 秒              移动 84,012,798 / N ^ 1.242 比较 82,844,399 / N ^ 1.241
法师改良 前后互质的 Sedgewick 双公式 序列:2354689, 1045055, 587527, 260609, 146309, 64763, 36293, 16001, 8929, 3907, 2161, 929, 503, 211, 109, 41, 19, 5, 1
用时 36.039 秒              移动 85,484,188 / N ^ 1.243 比较 84,233,821 / N ^ 1.242


嗯,Ciura  序列确实快一些。把序列搞全就好了,至少要到一千万。



作者: liucqa    时间: 2013-4-25 15:21
lee1892 发表于 2013-4-25 13:25
701以后都是这哥们不知道哪抄来的吧,我用的是:h(k) = INT(2.25 * h(k-1)),他这个应该是:h(k) = INT(7 ...


Ciura 换成部分质数序列貌似快点

希尔排序中不同步长序列的对比:
随机单精度数据数量:1,000,000
Ciura 的 部分质数序列:460451, 204641, 90947, 40427, 17971, 7993, 3547, 1579, 701, 307, 131, 57, 23, 9, 4, 1
用时 11.902 秒              移动 32,932,455 / N ^ 1.253 比较 32,431,147 / N ^ 1.252
Ciura 的 序列:460445, 204643, 90952, 40423, 17965, 7985, 3549, 1577, 701, 301, 132, 57, 23, 9, 4, 1
用时 12.543 秒              移动 32,524,887 / N ^ 1.252 比较 32,022,997 / N ^ 1.251
法师改良 前后互质的 Sedgewick 双公式 序列:587527, 260609, 146309, 64763, 36293, 16001, 8929, 3907, 2161, 929, 503, 211, 109, 41, 19, 5, 1
用时 13.445 秒              移动 33,162,505 / N ^ 1.253 比较 32,646,279 / N ^ 1.252

希尔排序中不同步长序列的对比:
随机单精度数据数量:500,000
Ciura 的 部分质数序列:460451, 204641, 90947, 40427, 17971, 7993, 3547, 1579, 701, 307, 131, 57, 23, 9, 4, 1
用时 6.320 秒 移动 15,467,034 / N ^ 1.262 比较 15,228,557 / N ^ 1.260
Ciura 的 序列:460445, 204643, 90952, 40423, 17965, 7985, 3549, 1577, 701, 301, 132, 57, 23, 9, 4, 1
用时 6.535 秒 移动 15,310,490 / N ^ 1.261 比较 15,072,301 / N ^ 1.260
法师改良 前后互质的 Sedgewick 双公式 序列:260609, 146309, 64763, 36293, 16001, 8929, 3907, 2161, 929, 503, 211, 109, 41, 19, 5, 1
用时 6.660 秒 移动 15,652,105 / N ^ 1.262 比较 15,377,516 / N ^ 1.261





作者: lee1892    时间: 2013-4-25 15:31
liucqa 发表于 2013-4-25 15:21
Ciura 换成部分质数序列貌似快点

希尔排序中不同步长序列的对比:

按原论文,701后面一个是1750

再后面的都不是Ciura序列了,是拿2.25乘出来的~

1、没有数学上的证明,仅靠几次测试随机数是说明不了问题的
2、快速排序在大数量数据排序时可以轻易的击败希尔排序,所以从根上说,研究希尔排序是数学家的事,咱没必要参合的
3、希尔排序的实际应用实在是太少了,当然代码写起来倒是蛮方便的


作者: liucqa    时间: 2013-4-25 16:04
lee1892 发表于 2013-4-25 15:31
按原论文,701后面一个是1750

再后面的都不是Ciura序列了,是拿2.25乘出来的~

不同的序列,在大数据量下,差距还是很可观的。

对俺这等数学盲来说,啥算法无所谓,如果能在希尔排序里面,找到一个更快的序列,那就用嘛。
要说证明,嗯...  俺的意见是,如果计算机跑10次,大部分时候都是某个序列快的话,那就当作是真快好了{:soso_e113:}

随机单精度数据数量:5,000,000
Ciura 的 序列:2331004, 1036002, 460445, 204643, 90952, 40423, 17965, 7985, 3549, 1577, 701, 301, 132, 57, 23, 9, 4, 1
用时 105.602 秒             移动 185,427,945 / N ^ 1.234              比较 182,904,249 / N ^ 1.233
Ciura 的 部分质数序列:2330959, 1036001, 460451, 204641, 90947, 40427, 17971, 7993, 3547, 1579, 701, 307, 131, 57, 23, 9, 4, 1
用时 95.973 秒              移动 186,994,537 / N ^ 1.235              比较 184,471,604 / N ^ 1.234
法师改良 前后互质的 Sedgewick 双公式 序列:4188161, 2354689, 1045055, 587527, 260609, 146309, 64763, 36293, 16001, 8929, 3907, 2161, 929, 503, 211, 109, 41, 19, 5, 1
用时 94.875 秒              移动 188,564,332 / N ^ 1.235              比较 185,962,704 / N ^ 1.234

随机单精度数据数量:300,000
Ciura 的 序列:204643, 90952, 40423, 17965, 7985, 3549, 1577, 701, 301, 132, 57, 23, 9, 4, 1
用时 4.059 秒 移动 8,749,473 / N ^ 1.267  比较 8,607,971 / N ^ 1.266
Ciura 的 部分质数序列:204641, 90947, 40427, 17971, 7993, 3547, 1579, 701, 307, 131, 57, 23, 9, 4, 1
用时 3.930 秒 移动 8,861,307 / N ^ 1.268  比较 8,719,886 / N ^ 1.267
法师改良 前后互质的 Sedgewick 双公式 序列:260609, 146309, 64763, 36293, 16001, 8929, 3907, 2161, 929, 503, 211, 109, 41, 19, 5, 1
用时 4.039 秒 移动 8,935,631 / N ^ 1.269  比较 8,777,861 / N ^ 1.268

随机单精度数据数量:10,000,000
Ciura 的 部分质数序列:5244763, 2330959, 1036001, 460451, 204641, 90947, 40427, 17971, 7993, 3547, 1579, 701, 307, 131, 57, 23, 9, 4, 1
用时 170.113 秒             移动 394,476,462 / N ^ 1.228              比较 389,258,290 / N ^ 1.227
Ciura 的 序列:5244759, 2331004, 1036002, 460445, 204643, 90952, 40423, 17965, 7985, 3549, 1577, 701, 301, 132, 57, 23, 9, 4, 1
用时 183.105 秒             移动 390,649,594 / N ^ 1.227              比较 385,431,311 / N ^ 1.227
法师改良 前后互质的 Sedgewick 双公式 序列:9427969, 4188161, 2354689, 1045055, 587527, 260609, 146309, 64763, 36293, 16001, 8929, 3907, 2161, 929, 503, 211, 109, 41, 19, 5, 1
用时 190.367 秒             移动 396,334,465 / N ^ 1.228              比较 391,201,441 / N ^ 1.227

俺不明白的是,为什么Ciura 原序列移动和比较的次数少,时间反而长呢?




作者: lee1892    时间: 2013-4-25 16:26
liucqa 发表于 2013-4-25 16:04
不同的序列,在大数据量下,差距还是很可观的。

对俺这等数学盲来说,啥算法无所谓,如果能在希尔排序 ...
  1. 俺不明白的是,为什么Ciura 原序列移动和比较的次数少,时间反而长呢?
复制代码
这我也不明白,貌似还和前后次序有关系,看上去你也注意到了。

或则你把法师招来讨论?
作者: liucqa    时间: 2013-4-25 17:22
lee1892 发表于 2013-4-25 16:26
这我也不明白,貌似还和前后次序有关系,看上去你也注意到了。

或则你把法师招来讨论?

前后次序问题,大概是你的代码写的不太对,在每次排序前,应该给排序的数组用循环方式从原始数组重新赋值,而不是用=号


  1. Option Explicit

  2. Sub TestShellSpeed()
  3.     Dim i&, t#, aData!(), bData!(), arr, j&, sMsg$, aGaps, nLen&
  4.     Dim nMov As Currency, nCom As Currency
  5.     nLen = 10 ^ 5 * 3    ' <-- 数据数量
  6.     ReDim aData(1 To nLen)
  7.     ReDim bData(1 To nLen)

  8.     Debug.Print
  9.     Debug.Print "希尔排序中不同步长序列的对比:"
  10.     Debug.Print "随机单精度数据数量:" & Format(nLen, "#,##")
  11.     Randomize
  12.     For j = 1 To UBound(aData)
  13.         aData(j) = Rnd
  14.     Next

  15.     For i = 0 To 2
  16.         For j = 1 To UBound(aData)
  17.             bData(j) = aData(j)
  18.         Next
  19.         Call GetShellGaps(aGaps, nLen, i, sMsg)
  20.         t = Timer
  21.         Call ShellSort(bData, aGaps, nMov, nCom)
  22.         Debug.Print sMsg & ":" & Join(aGaps, ", ")
  23.         Debug.Print Format(Timer - t, "用时 0.000 秒"), _
  24.                     Format(nMov, "移动 #,##") & " / N ^ " & Format(Log(nMov) / Log(nLen), "0.000"), _
  25.                     Format(nCom, "比较 #,##") & " / N ^ " & Format(Log(nCom) / Log(nLen), "0.000")
  26.     Next
  27. End Sub

  28. Sub ShellSort(ByRef arr, ByRef aGaps, _
  29.               Optional ByRef nMove As Currency, _
  30.               Optional ByRef nCompare As Currency)
  31.     Dim i&, j&, vTemp, nGap, nLen&
  32.     nLen = UBound(arr)
  33.     nMove = 0: nCompare = 0
  34.     For Each nGap In aGaps
  35.         For i = nGap + 1 To nLen
  36.             vTemp = arr(i)
  37.             For j = i To nGap + 1 Step nGap * -1
  38.                 nCompare = nCompare + 1
  39.                 If arr(j - nGap) < vTemp Then Exit For
  40.                 arr(j) = arr(j - nGap)
  41.                 nMove = nMove + 1
  42.             Next
  43.             arr(j) = vTemp: nMove = nMove + 1
  44.         Next
  45.     Next
  46. End Sub

  47. Sub GetShellGaps(ByRef arrGaps As Variant, _
  48.                  ByVal nArrLen As Currency, _
  49.                  Optional ByVal nGapType As Integer = 0, _
  50.                  Optional ByRef sMessage As String = "")
  51.     Dim i&, nNum&, aTemp, nCount&
  52.     Select Case nGapType
  53.     Case 1    ' Ciura\2001
  54.         sMessage = "Ciura 的 部分质数序列"
  55.         aTemp = Array(1, 4, 9, 23, 57, 131, 307, 701, 1579, 3547, 7993, 17971, 40427, 90947, 204641, 460451, 1036001, 2330959, 5244763)
  56.         For nNum = UBound(aTemp) To 0 Step -1
  57.             If aTemp(nNum) < nArrLen Then Exit For
  58.         Next
  59.     Case 0    ' Ciura\2001
  60.         sMessage = "Ciura 的 序列"
  61.         aTemp = Array(1, 4, 9, 23, 57, 132, 301, 701, 1577, 3549, 7985, 17965, 40423, 90952, 204643, 460445, 1036002, 2331004, 5244759)
  62.         For nNum = UBound(aTemp) To 0 Step -1
  63.             If aTemp(nNum) < nArrLen Then Exit For
  64.         Next
  65.     Case 2    ' Sedgewick\1986 双公式 法师改良 前后互质
  66.         sMessage = "法师改良 前后互质的 Sedgewick 双公式 序列"
  67.         aTemp = Array(1, 5, 19, 41, 109, 211, 503, 929, 2161, 3907, 8929, 16001, 36293, 64763, 146309, 260609, 587527, 1045055, 2354689, 4188161, 9427969)
  68.         For nNum = UBound(aTemp) To 0 Step -1
  69.             If aTemp(nNum) < nArrLen Then Exit For
  70.         Next
  71.     Case 6    ' Tokuda\1992
  72.         sMessage = "Tokuda 的 序列"
  73.         ReDim aTemp(0 To 10)
  74.         nNum = 0
  75.         Do
  76.             aTemp(nNum) = Int((9 ^ (nNum + 1) - 4 ^ (nNum + 1)) / (5 * 4 ^ nNum)) + IIf(nNum, 1, 0)
  77.             If aTemp(nNum) > nArrLen Then nNum = nNum - 1: Exit Do
  78.             nNum = nNum + 1
  79.             If UBound(aTemp) < nNum Then ReDim Preserve aTemp(0 To nNum + 10)
  80.         Loop
  81.     Case 7    ' Gonnet & Baeza-Yates\1991
  82.         sMessage = "Gonnet & Baeza-Yates 的 序列"
  83.         ReDim aTemp(0 To 10)
  84.         nNum = 0: aTemp(nNum) = Int(5 * nArrLen / 11)
  85.         Do
  86.             If aTemp(nNum) <= 1 Then
  87.                 aTemp(nNum) = 1
  88.                 ReDim Preserve aTemp(0 To nNum)
  89.                 arrGaps = aTemp
  90.                 Exit Sub
  91.             End If
  92.             nNum = nNum + 1
  93.             If UBound(aTemp) < nNum Then ReDim Preserve aTemp(0 To nNum + 10)
  94.             aTemp(nNum) = Int(5 * aTemp(nNum - 1) / 11)
  95.         Loop
  96.     Case 3    ' Sedgewick\1986 双公式
  97.         sMessage = "原本的 Sedgewick 双公式 序列"
  98.         ReDim aTemp(0 To 10)
  99.         nNum = 0: nCount = 1
  100.         Do
  101.             aTemp(nNum) = 9 * (4 ^ (nCount - 1) - 2 ^ (nCount - 1)) + 1
  102.             If aTemp(nNum) > nArrLen Then nNum = nNum - 1: Exit Do
  103.             nNum = nNum + 1
  104.             If UBound(aTemp) < nNum Then ReDim Preserve aTemp(0 To nNum + 10)
  105.             aTemp(nNum) = 4 ^ (nCount + 1) - 6 * 2 ^ nCount + 1
  106.             If aTemp(nNum) > nArrLen Then nNum = nNum - 1: Exit Do
  107.             nNum = nNum + 1
  108.             If UBound(aTemp) < nNum Then ReDim Preserve aTemp(0 To nNum + 10)
  109.             nCount = nCount + 1
  110.         Loop
  111.     Case 4    ' Sedgewick\1986 单公式
  112.         sMessage = "Sedgewick 单公式 序列"
  113.         ReDim aTemp(0 To 10)
  114.         aTemp(0) = 1: nNum = 1
  115.         Do
  116.             aTemp(nNum) = 4 ^ nNum + 3 * 2 ^ (nNum - 1) + 1
  117.             If aTemp(nNum) > nArrLen Then nNum = nNum - 1: Exit Do
  118.             nNum = nNum + 1
  119.             If UBound(aTemp) < nNum Then ReDim Preserve aTemp(0 To nNum + 10)
  120.         Loop
  121.     Case 5    ' 基于 Fibonacci
  122.         sMessage = "基于费波那契数列的 序列"
  123.         aTemp = Array(1, 9, 34, 182, 835, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713, 2147483647)
  124.         For nNum = UBound(aTemp) To 0 Step -1
  125.             If aTemp(nNum) < nArrLen Then Exit For
  126.         Next

  127.     End Select
  128.     ReDim arrGaps(0 To nNum)
  129.     For i = 0 To nNum
  130.         arrGaps(i) = aTemp(nNum - i)
  131.     Next
  132. End Sub
复制代码



作者: liucqa    时间: 2013-4-25 17:38
lee1892 发表于 2013-4-25 12:50
内省排序(IntroSort)

内省排序结合了快速排序、插入排序以及堆排序,充分利用了各自的优点,其运作方式 ...

http://www.cnblogs.com/imAkaka/articles/2407877.html

STL sort源码剖析
作者: 灰袍法师    时间: 2013-4-25 18:05
本帖最后由 灰袍法师 于 2013-4-25 21:02 编辑
lee1892 发表于 2013-4-25 16:26
这我也不明白,貌似还和前后次序有关系,看上去你也注意到了。

或则你把法师招来讨论?

我的猜想是:比较和移动更多地是在“附近”的地址,所以CPU的高速缓冲有更大的命中率。
这就可以在比较+移动次数更多的时候,总耗时反而更低。
也许可以把最后几次步长较低的 比较和移动 去掉,不计入总数,就可以看出是不是这个问题。

另一方面,似乎应该用 编译程序 来测试,VBA本身有些什么因素会影响代码速度,我也搞不清楚。

然后就是楼主的质疑:为什么发布希尔排序序列的人,不发布快一点的质数序列,而是发布公式计算出来的序列。
这个我也搞不清楚。
估计是:质数序列实际上并不能做到对 任何情况 都比 原始序列好,所以没必要这么计较。


作者: xianshu    时间: 2013-4-25 18:55
谢谢了,楼主!
作者: 灰袍法师    时间: 2013-4-25 20:56
lee1892 发表于 2013-4-24 15:50
对于快速排序而言,数据量的大小并不会是导致堆栈溢出的主要原因,而是数据是否是精心设计过的。

而所 ...

实际上,一个乱序数组是不太可能造成堆栈溢出的,比如在我的机器上单精度数组最大可申请到10^7 ~ 10^8 之间,如果你愿意的话,可以反复测试下述代码是否会堆栈溢出,呵呵:
说实在的,我很怀疑坛子里有几个人能设计出这样的顺序,嘿嘿~
=========================================
我就是那个很倒霉的人,在我写我的排序贴时候,就碰到快速排序运行了几十秒(正常只要几秒。。。。。。我还以为死循环了。)
但是。。。仅此一次,以后再也没碰到过了。

《计算机程序设计的艺术》一书,提到如果采用随机分割值,对于随机生成的数据,
出现退化的概率低于 一千万分之一,退化定义为程序的时间复杂度是超过 20*N*logN

所以,随机数据+随机分割的快速排序,还真的不是想象中的那么“绝对安全”
在完全不能接受任何一次排序出现 耗时20倍 的要求下,单用随机分割的快速排序就不够好了。

当然,对于一般公司数据排序,学校学生排名之类,随机分割的快速排序完全没有任何问题。

作者: mjzxlmg    时间: 2013-4-25 21:25
灰袍法师 发表于 2013-4-25 20:56
实际上,一个乱序数组是不太可能造成堆栈溢出的,比如在我的机器上单精度数组最大可申请到10^7 ~ 10^8 之 ...

temp_h = Array(1, 5, 19, 41, 109, 211, 503, 929, 2161, 3907, 8929, 16001, 36293, 64763, 146309, 260609, 587527, 1045061, 2354701, 4188161, 9427967, 16764901, 37730309, 67084289, 150958081)



aTemp = Array(1, 5, 19, 41, 109, 211, 503, 929, 2161, 3907, 8929, 16001, 36293, 64763, 146309, 260609, 587527, 1045055, 2354689, 4188161, 9427969)


搞不明白,与数列个数有关系吗?


作者: wyxsg888    时间: 2013-4-25 22:14
太牛了,下载后慢慢消化。
作者: 灰袍法师    时间: 2013-4-25 22:48
mjzxlmg 发表于 2013-4-25 21:25
temp_h = Array(1, 5, 19, 41, 109, 211, 503, 929, 2161, 3907, 8929, 16001, 36293, 64763, 146309, 26 ...

希尔排序的H数组,决定了能够处理多大规模的排序,只看最大数字,然后乘以10就差不多了。
最大数字是900万的话,可以高效处理 9000万规模的排序问题。
因此,我们希望如果有一个高效的H序列,那么这个序列的最大数字最好也比较大,可以应付大规模的排序问题。

上面说的堆栈溢出,是针对快速排序而言,希尔排序不会有这个溢出的问题。
作者: mjzxlmg    时间: 2013-4-25 23:44
灰袍法师 发表于 2013-4-25 22:48
希尔排序的H数组,决定了能够处理多大规模的排序,只看最大数字,然后乘以10就差不多了。
最大数字是900 ...

谢谢指导,努力学习。
作者: lee1892    时间: 2013-4-26 09:39
灰袍法师 发表于 2013-4-25 20:56
实际上,一个乱序数组是不太可能造成堆栈溢出的,比如在我的机器上单精度数组最大可申请到10^7 ~ 10^8 之 ...
我就是那个很倒霉的人,在我写我的排序贴时候,就碰到快速排序运行了几十秒(正常只要几秒。。。。。。我还以为死循环了。)
但是。。。仅此一次,以后再也没碰到过了。

你完全应该去买彩票了,数10万、百万规模的随机,都能碰到~{:soso_e113:}
作者: endend1980    时间: 2013-4-26 20:51
对于我这样一个VBA新手来说,真是看不懂,但我特想知道能把VBA研究的这么深的会是做什么,是不是每天都要跟VBA打交道,如果只是凭着兴趣去学习,而工作中根本就用不到的话应该学不了这么深吧!
作者: 白云人家    时间: 2013-4-28 11:04
i学习,学习了
作者: jiangdong110    时间: 2013-4-29 08:53
晕,落后太多,简直看不懂!
作者: chenzyyysl    时间: 2013-4-30 16:35
学个印象,以后有用到再来研究
作者: iewihz    时间: 2013-5-1 08:47
向高手学习、致敬啦,谢谢!
作者: netpig    时间: 2013-5-1 08:55
太牛了。留下足印,慢慢学习。
作者: xxxasdf    时间: 2013-5-1 09:43
先收藏,再学习!
作者: jrllchuan    时间: 2013-5-1 13:27
好贴,学习了。谢谢!!!{:soso_e181:}
作者: zxzxcl    时间: 2013-5-1 14:40
篇篇都要珍藏

作者: funfunlai    时间: 2013-5-1 16:41
留个记号,慢慢学
作者: 834222188    时间: 2013-5-1 20:10
好东东  谢谢分享  楼主
作者: name004    时间: 2013-5-4 09:37
赶紧做个记号,回头再看
作者: 香川群子    时间: 2013-5-4 12:46
endend1980 发表于 2013-4-26 20:51
对于我这样一个VBA新手来说,真是看不懂,但我特想知道能把VBA研究的这么深的会是做什么,是不是每天都要跟 ...

排序算法是有专家研究的。

但或许并没有以研究排序算法为职业的人。

因为这个是靠天才和钻研和运气才能出成果的。


并不是一个大学生、研究生或者博士生,给他工资,让他专门研究一辈子,就一定会有成果出来的。


…………
这个世界上是有天才存在的。天才和普通人之间的思维差别,是几百甚至上千倍。

我们普通人,能把天才研究出来的东西看懂,也就可以算是一个人才了。


作者: FENDOU2013    时间: 2013-5-12 09:32
{:soso_e100:}学习
作者: thjszxzdy    时间: 2013-5-12 12:37
lee1892 发表于 2013-4-26 09:39
你完全应该去买彩票了,数10万、百万规模的随机,都能碰到~

http://club.excelhome.net/forum. ... p;extra=#pid6928266
一个人的求助,既然对排序这么有研究,研究这个不是很难的。数据可以加一个负号,然后变为全加法的数据。进行数组内加法计算。合适的填充。写好后给我一份吧。
作者: gyc978    时间: 2013-5-17 09:42
支持楼主!!!!!!!!
作者: 香川群子    时间: 2013-5-17 11:45
thjszxzdy 发表于 2013-5-12 12:37
http://club.excelhome.net/forum.php?mod=viewthread&tid=1016386&page=1&extra=#pid6928266
一个人的求 ...

你提供链接的那个问题,不是排序问题。和本楼无关。

是组合问题。

组合方面我是高手。 问题我已经解决了。你直接去看20楼的附件代码吧。


作者: relaxg    时间: 2013-5-26 08:26
希望持续更新
作者: uyi157    时间: 2013-5-31 09:22
得好好学习。楼主辛苦了!{:soso_e183:}
作者: shuimushenguang    时间: 2013-5-31 16:53
学习一下,排序很重要
作者: zez    时间: 2013-6-1 08:14
排序很重要,收藏学习!
作者: jrsyb    时间: 2013-6-6 21:18
感觉好复杂啊,作个记号,我要学会,很需要
作者: jiangwh15    时间: 2013-6-9 14:09
好贴,谢谢分享!
作者: 为射门    时间: 2013-6-15 16:42
最为常见的顺序是 数值顺序 和 字符顺序。对于一些其它算法的优化,一个高效的排序算法是起决定性作用的,比如查找、合并等。

作者: xwenwei    时间: 2013-6-16 00:38
谢谢了,楼主!
作者: sbhly819    时间: 2013-6-16 16:51
向高手学习、谢谢分享!
作者: CAPTAINJACK    时间: 2013-6-18 18:21
好复杂  抱着学习的心态来看了~
作者: wqfzqgk    时间: 2013-6-19 09:36
看了看,晕头转向,看不懂啊
作者: minjiwei    时间: 2013-6-19 11:11
好贴,收藏了,谢谢啊
作者: wwwruc    时间: 2013-6-20 10:03
好东西啊,楼主研究的真好。
作者: I000000I    时间: 2013-6-26 10:38
看的眼花缭乱啊,膜拜一下。
等进化了再来消化,楼主辛苦了
作者: guojianlin1985    时间: 2013-6-26 22:11
受益匪浅。收藏研读
作者: lzqmsy    时间: 2013-6-27 18:01
做个记号,学习方便,谢谢楼主,真的非常好
作者: pxla    时间: 2013-6-28 09:34
学习了一下
作者: xyunal    时间: 2013-7-3 09:23
一直想系统的学习VBA
作者: 尤_文    时间: 2013-7-3 14:40
学习了~{:soso_e129:}
作者: wgw6288    时间: 2013-7-3 16:54
要是有实例就好,就能看得懂些,只是VBA看蒙了
作者: jrllchuan    时间: 2013-7-7 16:33
最近在找的资料,楼主介绍的有点难。有空学习下。
作者: morihui    时间: 2013-7-7 22:37
哇,很好,我要好好学习一下
作者: nuzzll    时间: 2013-7-9 20:37
这个必须收藏,谢谢楼主!
作者: danysy    时间: 2013-7-12 08:38
值得学习,谢谢啦
作者: lbpp    时间: 2013-7-12 09:49
很好的排序教程。不错不错。

作者: aierb    时间: 2013-7-12 10:00

做个记号,学习方便,谢谢楼主,真的非常好
作者: name004    时间: 2013-7-13 21:00
排序算法--云雾之中,
作者: ddldel    时间: 2013-7-16 09:44
太厉害了,学习学习学习
作者: ddldel    时间: 2013-7-16 11:40
顶一个,支持
作者: 鱼纸妹    时间: 2013-7-16 21:07
学习一下,楼主强大
作者: ghh5599    时间: 2013-7-19 08:47
太高深了,有点看不懂啊。。。
作者: leolee82    时间: 2013-7-19 11:19
谢谢楼主的分享,支持下
1. 个人认为算法是纯理论的东西,可以完全脱离计算机语言去研究.
要说语言的话,感觉C++更适合计算通用算法. 毕竟C++可以是面向对象的,运算符和函数重载,函数回调和模板可以大大增强算法的通用性/方便使用. STL是最好的例子. 但C++的异常处理和操作com对象就显然不如VB/c#/JAVA之类的了,即使有ATL, 相对来说也很麻烦,响应个事件就要继承N个类,添加映射. 编译也慢.

2. 至于那个交换次数多但速度快的算法应该如法师所说是cpu缓存的原因. 这个应该算是硬件的局限性吧

另外,请教下:
1.  VBA中对于传入算法的比较规则, 一直没有个很优雅的解决方案, 不知道楼主有好办法没
2.  不知楼主有没有研究过C++中用STL处理从Excel中读入的VARIANT数组, 还望分享讨论下(不知EH会不会限制讨论VB/vsto之外的内容).
     因为行列都是动态的, 貌似只能写个VARIANT数据的二维数组包装类,还要设计迭代器. 不知楼主有其他更好的想法没.
作者: lee1892    时间: 2013-7-19 11:54
leolee82 发表于 2013-7-19 11:19
谢谢楼主的分享,支持下
1. 个人认为算法是纯理论的东西,可以完全脱离计算机语言去研究.
要说语言的话,感 ...

嗯,你找错讨论对象了,呵呵~

我属于票友,只能写些科普的东东娱乐大众~~
作者: leolee82    时间: 2013-7-19 13:04
lee1892 发表于 2013-7-19 11:54
嗯,你找错讨论对象了,呵呵~

我属于票友,只能写些科普的东东娱乐大众~~

彼此彼此, 我比较懒, 只能自娱自乐.
楼主显然是高手, 因为算法才是灵魂,语言只是个肉体而已
作者: lucliang    时间: 2013-7-23 11:18
感谢分享:)
作者: ericer    时间: 2013-8-8 16:03
好东西,好好学习




欢迎光临 ExcelHome技术论坛 (https://club.excelhome.net/) Powered by Discuz! X3.4