該比武只比速度，單線程測(cè)試隨機(jī)正整數(shù)，不包括蝸牛排序，它棄權(quán)啦，哈哈。
操作系統(tǒng)：Windows XP Pro SP3，英文版
編譯器：g++4.5.2(-O3)
CPU： Intel Core2 Q9500
內(nèi)存：DDR3普條 1066MHz， 4GB
插入排序、選擇排序和冒泡排序最慢，時(shí)間復(fù)雜度為O(n2)，希爾排序的速度依賴于使用的增量序列，堆排序、歸并排序和改進(jìn)的快速排序處于中等水平，時(shí)間復(fù)雜度為O(nlogn)，計(jì)數(shù)排序、基數(shù)排序以及桶排序最快，時(shí)間復(fù)雜度為O(n)。
前面已經(jīng)說過，標(biāo)準(zhǔn)庫(kù)中收錄了堆排序、改進(jìn)的快速排序和歸并排序，它們的理論速度處于中上等水平，卻沒有收錄理論速度更快的計(jì)數(shù)排序、基數(shù)排序和桶排序中的任何一種，這究竟因?yàn)楹喂?？相信太多人弄不明白其中的道理。原因其?shí)很簡(jiǎn)單，因?yàn)闀r(shí)間復(fù)雜度為O(n)的這三種排序?qū)嶋H表現(xiàn)不佳，空間開銷太大，且具體實(shí)現(xiàn)嚴(yán)重依賴數(shù)據(jù)類型。
為了檢驗(yàn)上述排序算法的性能，用隨機(jī)數(shù)序列做了正序排序測(cè)試，除了計(jì)數(shù)排序外，其它排序測(cè)試數(shù)值范圍為[0, 2147483648)，各種排序耗費(fèi)的時(shí)間見下表。
簡(jiǎn)單比較排序，時(shí)間復(fù)雜度一般為O(n2)，希爾排序的時(shí)間復(fù)雜度依賴于使用的序列，使用Hibbard序列時(shí)，希爾排序時(shí)間復(fù)雜度最差為O(n3/2)，使用Sedgewick序列時(shí)，希爾排序時(shí)間復(fù)雜度最差為O(n4/3)，簡(jiǎn)單排序的空間復(fù)雜度均為O(1)。
把一個(gè)隨機(jī)序列排序成升序序列(單位：毫秒)。
| 數(shù)據(jù)量 | 插入排序 | 選擇排序 | 冒泡排序 | 希爾排序 |
| 直接插入 | 二分插入 | Hibbard | Sedgewick |
| 1.0e+1 | 0.000525 | 0.000638 | 0.000700 | 0.000651 | 0.000570 | 0.000689 |
| 1.0e+2 | 0.004058 | 0.006403 | 0.010846 | 0.017810 | 0.004805 | 0.005292 |
| 1.0e+3 | 0.248739 | 0.241721 | 0.709755 | 1.76696 | 0.075513 | 0.075307 |
| 1.0e+4 | 23.6821 | 18.5430 | 65.0864 | 175.155 | 1.13762 | 1.11278 |
| 1.0e+5 | 2334.46 | 1799.45 | 6445.43 | 17642.6 | 15.4906 | 15.7181 |
| 1.0e+6 | 241898 | 188869 | 660667 | 1819720 | 218.087 | 206.449 |
| 1.0e+7 | --- | --- | --- | --- | 2892.09 | 2731.79 |
| 1.0e+8 | --- | --- | --- | --- | 39645.8 | 30624.1 |
把一個(gè)升序序列排序成升序序序列(單位：毫秒)。
| 數(shù)據(jù)量 | 插入排序 | 選擇排序 | 冒泡排序 | 希爾排序 |
| 直接插入 | 二分插入 | Hibbard | Sedgewick |
| 1.0e+1 | 0.000431 | 0.000497 | 0.000576 | 0.000413 | 0.000471 | 0.000604 |
| 1.0e+2 | 0.000705 | 0.001689 | 0.007730 | 0.000515 | 0.001762 | 0.002578 |
| 1.0e+3 | 0.005211 | 0.023300 | 0.654459 | 0.001495 | 0.024479 | 0.026534 |
| 1.0e+4 | 0.032183 | 0.261476 | 64.6679 | 0.011198 | 0.387672 | 0.383410 |
| 1.0e+5 | 0.326892 | 3.31448 | 6462.27 | 0.106789 | 5.00605 | 5.11000 |
| 1.0e+6 | 3.25322 | 40.2028 | 661825 | 1.14374 | 66.9433 | 66.3024 |
| 1.0e+7 | 31.2321 | 477.013 | --- | 11.9349 | 828.123 | 803.050 |
| 1.0e+8 | 306.505 | 5550.34 | --- | 118.441 | 9476.97 | 9471.65 |
把一個(gè)降序序列排序成升序序列(單位：毫秒)。
| 數(shù)據(jù)量 | 插入排序 | 選擇排序 | 冒泡排序 | 希爾排序 |
| 直接插入 | 二分插入 | Hibbard | Sedgewick |
| 1.0e+1 | 0.000528 | 0.000580 | 0.000633 | 0.000512 | 0.000462 | 0.000618 |
| 1.0e+2 | 0.004795 | 0.005481 | 0.008988 | 0.006476 | 0.0025228 | 0.003193 |
| 1.0e+3 | 0.362995 | 0.376571 | 0.690305 | 0.539237 | 0.0324535 | 0.033210 |
| 1.0e+4 | 35.5184 | 35.6372 | 67.7467 | 65.3332 | 0.510507 | 0.447574 |
| 1.0e+5 | 3546.92 | 3546.18 | 6776.27 | 8990.63 | 6.42464 | 5.74839 |
| 1.0e+6 | 432377 | 431580 | 694979 | 617435 | 83.7521 | 79.7468 |
| 1.0e+7 | --- | --- | --- | --- | 988.176 | 949.626 |
| 1.0e+8 | --- | --- | --- | --- | 11734.7 | 11063.1 |
從上面三個(gè)表可以看出，當(dāng)數(shù)據(jù)量很小時(shí)，直接插入排序由于開銷很小，因此速度很快。當(dāng)一個(gè)序列已經(jīng)有序時(shí)，冒泡排序速度最快，其它情況，冒泡排序的速度最慢(本文沒有針對(duì)這種情況給出更詳細(xì)的測(cè)試結(jié)果)。盡管希爾排序僅僅是插入排序的一個(gè)變種，但是在一般場(chǎng)合，希爾排序的速度會(huì)遙遙領(lǐng)先于插入排序，甚至可以與時(shí)間復(fù)雜度為O(nlogn)的堆排序匹敵。
復(fù)雜的比較排序，時(shí)間復(fù)雜度一般為O(nlogn)，原地歸并排序時(shí)間復(fù)雜度為O(nlog2n)。堆排序的空間復(fù)雜度為O(1)，快速排序和原地歸并排序的空間復(fù)雜度一般為O(logn)，帶緩沖區(qū)的歸并排序的空間復(fù)雜度一般為O(n)。
把一個(gè)隨機(jī)序列排序成升序序列(單位：毫秒)。
| 數(shù)據(jù)量 | 堆排序 | 快速排序 | 歸并排序 |
| sort | sort_r | quick_sort | qsort | 原地歸并 | 有緩沖區(qū) |
| 1.0e+1 | 0.000642 | 0.000540 | 0.000541 | 0.000706 | 0.000868 | 0.000535 | 0.000716 |
| 1.0e+2 | 0.005120 | 0.003417 | 0.003409 | 0.005350 | 0.008928 | 0.013398 | 0.003947 |
| 1.0e+3 | 0.064826 | 0.041792 | 0.042142 | 0.062889 | 0.117883 | 0.256407 | 0.048691 |
| 1.0e+4 | 0.826593 | 0.536043 | 0.539067 | 0.755660 | 1.50353 | 4.17856 | 0.633436 |
| 1.0e+5 | 10.7042 | 6.59608 | 6.62956 | 8.84884 | 18.3578 | 55.4733 | 7.91912 |
| 1.0e+6 | 158.744 | 78.4110 | 79.1261 | 101.926 | 214.367 | 697.286 | 99.3735 |
| 1.0e+7 | 3773.92 | 912.128 | 927.636 | 1152.59 | 2530.75 | 8810.93 | 1137.64 |
| 1.0e+8 | 60973.9 | 10352.9 | 10516.4 | 12822.2 | 28351.3 | 105516 | 13091.4 |
把一個(gè)升序序列排序成升序序列(單位：毫秒)。
| 數(shù)據(jù)量 | 堆排序 | 快速排序 | 歸并排序 |
| sort | sort_r | quick_sort | qsort | 原地歸并 | 有緩沖區(qū) |
| 1.0e+1 | 0.000513 | 0.000435 | 0.000439 | 0.000506 | 0.000595 | 0.000433 | 0.000602 |
| 1.0e+2 | 0.003738 | 0.001177 | 0.001394 | 0.002452 | 0.003632 | 0.002530 | 0.001744 |
| 1.0e+3 | 0.055996 | 0.008555 | 0.012148 | 0.019437 | 0.044580 | 0.024222 | 0.014240 |
| 1.0e+4 | 0.545597 | 0.115373 | 0.138347 | 0.200567 | 0.521049 | 0.335698 | 0.162571 |
| 1.0e+5 | 5.95518 | 1.18510 | 1.60851 | 2.14343 | 6.21663 | 2.71505 | 2.00932 |
| 1.0e+6 | 70.4104 | 11.8008 | 18.5488 | 25.5529 | 75.1664 | 24.1894 | 38.5684 |
| 1.0e+7 | 803.386 | 157.113 | 211.240 | 281.599 | 880.122 | 349.296 | 439.614 |
| 1.0e+8 | 9262.68 | 1653.56 | 2526.51 | 2994.46 | 9633.74 | 2792.79 | 5093.96 |
把一個(gè)降序序列排序成升序序列(單位：毫秒)。
| 數(shù)據(jù)量 | 堆排序 | 快速排序 | 歸并排序 |
| sort | sort_r | quick_sort | qsort | 原地歸并 | 有緩沖區(qū) |
| 1.0e+1 | 0.000533 | 0.000488 | 0.000501 | 0.000508 | 0.000674 | 0.000498 | 0.000611 |
| 1.0e+2 | 0.003663 | 0.001053 | 0.001488 | 0.002456 | 0.004197 | 0.004880 | 0.001840 |
| 1.0e+3 | 0.054465 | 0.007733 | 0.013793 | 0.019849 | 0.049924 | 0.055198 | 0.015355 |
| 1.0e+4 | 0.590327 | 0.106844 | 0.152277 | 0.203784 | 0.578746 | 0.729590 | 0.172541 |
| 1.0e+5 | 6.52191 | 1.10164 | 1.72681 | 2.16512 | 6.79996 | 7.61116 | 2.14922 |
| 1.0e+6 | 79.4964 | 12.3473 | 19.2062 | 25.5790 | 79.5690 | 82.7066 | 40.8505 |
| 1.0e+7 | 928.131 | 164.947 | 218.357 | 288.926 | 922.900 | 1127.96 | 460.994 |
| 1.0e+8 | 10697.4 | 1737.03 | 2468.51 | 3067.36 | 10074.7 | 13125.3 | 5327.67 |
可以看出，在時(shí)間復(fù)雜度為O(nlogn)的排序算法里，堆排序最慢，優(yōu)化的快速排序sort排序速度最快，隨機(jī)選取支點(diǎn)的快速排序sort_r僅次于sort，當(dāng)對(duì)一個(gè)隨機(jī)序列排序時(shí)，二者速度差距很小，原始的快速排序quick_sort(用了兩個(gè)遞歸)速度比較慢，可以看出，遞歸程序的執(zhí)行效率還是很低的，C庫(kù)函數(shù)qsort在幾個(gè)版本的快速排序里面墊底，主要原因是比較函數(shù)無法被編譯器內(nèi)聯(lián)。原地歸并排序雖然穩(wěn)定且節(jié)約內(nèi)存，但速度最慢，帶緩沖區(qū)的歸并排序速度還是蠻不錯(cuò)的。
理論時(shí)間復(fù)雜度為O(n)的計(jì)數(shù)排序、基數(shù)排序和桶排序的空間復(fù)雜度均為O(n)，且只能針對(duì)特殊數(shù)據(jù)類型排序，排序速度跟具體實(shí)現(xiàn)也有很大關(guān)系。
把一個(gè)隨機(jī)序列排序成升序序列(單位：毫秒)。
| 數(shù)據(jù)量 | 計(jì)數(shù)排序 | 基數(shù)排序 | 桶排序 |
| 1.0e+1 | 400.842 | 0.074379 | 0.001169 |
| 1.0e+2 | 488.821 | 0.077817 | 0.005455 |
| 1.0e+3 | 500.421 | 0.106693 | 0.053476 |
| 1.0e+4 | 500.097 | 0.376948 | 0.423485 |
| 1.0e+5 | 515.160 | 3.30198 | 5.24631 |
| 1.0e+6 | 666.797 | 63.2423 | 74.9957 |
| 1.0e+7 | 2254.77 | 1208.84 | 1024.32 |
| 1.0e+8 | 21174.0 | 14565.8 | 20708.8 |
把一個(gè)升序序列排序成升序序列(單位：毫秒)。
| 數(shù)據(jù)量 | 計(jì)數(shù)排序 | 基數(shù)排序 | 桶排序 |
| 1.0e+1 | 386.154 | 0.075321 | 0.001019 |
| 1.0e+2 | 487.709 | 0.079056 | 0.002017 |
| 1.0e+3 | 496.003 | 0.108765 | 0.013471 |
| 1.0e+4 | 499.207 | 0.379271 | 0.125317 |
| 1.0e+5 | 506.460 | 3.35299 | 1.64946 |
| 1.0e+6 | 550.123 | 62.4690 | 25.2364 |
| 1.0e+7 | 778.383 | 1199.67 | 269.743 |
| 1.0e+8 | 1878.57 | 15381.4 | 2771.17 |
把一個(gè)降序序列排序成升序序列(單位：毫秒)。
| 數(shù)據(jù)量 | 計(jì)數(shù)排序 | 基數(shù)排序 | 桶排序 |
| 1.0e+1 | 398.474 | 0.075307 | 0.001106 |
| 1.0e+2 | 489.401 | 0.079179 | 0.006004 |
| 1.0e+3 | 495.684 | 0.103746 | 0.062618 |
| 1.0e+4 | 500.081 | 0.339944 | 0.451859 |
| 1.0e+5 | 505.583 | 3.23047 | 5.83522 |
| 1.0e+6 | 525.979 | 61.7166 | 75.5025 |
| 1.0e+7 | 774.020 | 1209.40 | 595.325 |
| 1.0e+8 | 1697.88 | 15648.1 | 6643.6 |
對(duì)比計(jì)數(shù)排序、基數(shù)排序和桶排序的測(cè)試結(jié)果容易看出，這三款時(shí)間復(fù)雜度為O(n)的排序算法速度相差不大，對(duì)一個(gè)隨機(jī)整數(shù)序列的排序時(shí)，基數(shù)排序略占上風(fēng)。
時(shí)間復(fù)雜度為O(n)的計(jì)數(shù)排序、基數(shù)排序和桶排序均跟不上時(shí)間復(fù)雜度為O(nlogn))的快速排序sort的腳步，原因詳見本主頁(yè)基數(shù)排序。