排序方式 | 排序算法 |
交换排序(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) ... |
其它 | ... |
符号 | 名称 | 备注 |
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!) | 阶乘(阶) |
名称 | 稳定性 | 最佳时间复杂度 | 平均时间复杂度 | 最差时间复杂度 | 空间复杂度 | 排序方式 |
冒泡排序 | 是 | 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) | 插入 |
名称 | 稳定性 | 最佳时间复杂度 | 平均时间复杂度 | 最差时间复杂度 | 空间复杂度 | 排序方式 |
合并排序 | 是 | 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) | 插入 |
插入排序 | 希尔排序 |
[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] |
公式 | 序列数值 | 最坏情况的时间复杂度 | 作者/年份 |
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, ... | 未知 | 在大数组中有优异表现 |
代码: |
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 |
代码: |
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 |
liucqa 发表于 2013-4-25 00:24
http://www.doc88.com/p-905591811549.html
有空测试一下这个论文的真假
代码: |
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 |
liucqa 发表于 2013-4-25 13:15
http://blog.csdn.net/hustxifangshibai/article/details/619620
/*
lee1892 发表于 2013-4-25 13:25
701以后都是这哥们不知道哪抄来的吧,我用的是:h(k) = INT(2.25 * h(k-1)),他这个应该是:h(k) = INT(h ...
lee1892 发表于 2013-4-25 13:25
701以后都是这哥们不知道哪抄来的吧,我用的是:h(k) = INT(2.25 * h(k-1)),他这个应该是:h(k) = INT(7 ...
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 ...
我就是那个很倒霉的人,在我写我的排序贴时候,就碰到快速排序运行了几十秒(正常只要几秒。。。。。。我还以为死循环了。)
但是。。。仅此一次,以后再也没碰到过了。
thjszxzdy 发表于 2013-5-12 12:37
http://club.excelhome.net/forum.php?mod=viewthread&tid=1016386&page=1&extra=#pid6928266
一个人的求 ...
欢迎光临 ExcelHome技术论坛 (https://club.excelhome.net/) | Powered by Discuz! X3.4 |