该比武只比速度，单线程测试随机正整数，不包括蜗牛排序，它弃权啦，哈哈。
操作系统：Windows XP Pro SP3，英文版
编译器：g++4.5.2(-O3)
CPU： Intel Core2 Q9500
内存：DDR3普条 1066MHz， 4GB
插入排序、选择排序和冒泡排序最慢，时间复杂度为O(n2)，希尔排序的速度依赖于使用的增量序列，堆排序、归并排序和改进的快速排序处于中等水平，时间复杂度为O(nlogn)，计数排序、基数排序以及桶排序最快，时间复杂度为O(n)。
前面已经说过，标准库中收录了堆排序、改进的快速排序和归并排序，它们的理论速度处于中上等水平，却没有收录理论速度更快的计数排序、基数排序和桶排序中的任何一种，这究竟因为何故？相信太多人弄不明白其中的道理。原因其实很简单，因为时间复杂度为O(n)的这三种排序实际表现不佳，空间开销太大，且具体实现严重依赖数据类型。
为了检验上述排序算法的性能，用随机数序列做了正序排序测试，除了计数排序外，其它排序测试数值范围为[0, 2147483648)，各种排序耗费的时间见下表。
简单比较排序，时间复杂度一般为O(n2)，希尔排序的时间复杂度依赖于使用的序列，使用Hibbard序列时，希尔排序时间复杂度最差为O(n3/2)，使用Sedgewick序列时，希尔排序时间复杂度最差为O(n4/3)，简单排序的空间复杂度均为O(1)。
把一个随机序列排序成升序序列(单位：毫秒)。
| 数据量 | 插入排序 | 选择排序 | 冒泡排序 | 希尔排序 |
| 直接插入 | 二分插入 | 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 |
把一个升序序列排序成升序序序列(单位：毫秒)。
| 数据量 | 插入排序 | 选择排序 | 冒泡排序 | 希尔排序 |
| 直接插入 | 二分插入 | 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 |
把一个降序序列排序成升序序列(单位：毫秒)。
| 数据量 | 插入排序 | 选择排序 | 冒泡排序 | 希尔排序 |
| 直接插入 | 二分插入 | 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 |
从上面三个表可以看出，当数据量很小时，直接插入排序由于开销很小，因此速度很快。当一个序列已经有序时，冒泡排序速度最快，其它情况，冒泡排序的速度最慢(本文没有针对这种情况给出更详细的测试结果)。尽管希尔排序仅仅是插入排序的一个变种，但是在一般场合，希尔排序的速度会遥遥领先于插入排序，甚至可以与时间复杂度为O(nlogn)的堆排序匹敌。
复杂的比较排序，时间复杂度一般为O(nlogn)，原地归并排序时间复杂度为O(nlog2n)。堆排序的空间复杂度为O(1)，快速排序和原地归并排序的空间复杂度一般为O(logn)，带缓冲区的归并排序的空间复杂度一般为O(n)。
把一个随机序列排序成升序序列(单位：毫秒)。
| 数据量 | 堆排序 | 快速排序 | 归并排序 |
| sort | sort_r | quick_sort | qsort | 原地归并 | 有缓冲区 |
| 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 |
把一个升序序列排序成升序序列(单位：毫秒)。
| 数据量 | 堆排序 | 快速排序 | 归并排序 |
| sort | sort_r | quick_sort | qsort | 原地归并 | 有缓冲区 |
| 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 |
把一个降序序列排序成升序序列(单位：毫秒)。
| 数据量 | 堆排序 | 快速排序 | 归并排序 |
| sort | sort_r | quick_sort | qsort | 原地归并 | 有缓冲区 |
| 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 |
可以看出，在时间复杂度为O(nlogn)的排序算法里，堆排序最慢，优化的快速排序sort排序速度最快，随机选取支点的快速排序sort_r仅次于sort，当对一个随机序列排序时，二者速度差距很小，原始的快速排序quick_sort(用了两个递归)速度比较慢，可以看出，递归程序的执行效率还是很低的，C库函数qsort在几个版本的快速排序里面垫底，主要原因是比较函数无法被编译器内联。原地归并排序虽然稳定且节约内存，但速度最慢，带缓冲区的归并排序速度还是蛮不错的。
理论时间复杂度为O(n)的计数排序、基数排序和桶排序的空间复杂度均为O(n)，且只能针对特殊数据类型排序，排序速度跟具体实现也有很大关系。
把一个随机序列排序成升序序列(单位：毫秒)。
| 数据量 | 计数排序 | 基数排序 | 桶排序 |
| 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 |
把一个升序序列排序成升序序列(单位：毫秒)。
| 数据量 | 计数排序 | 基数排序 | 桶排序 |
| 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 |
把一个降序序列排序成升序序列(单位：毫秒)。
| 数据量 | 计数排序 | 基数排序 | 桶排序 |
| 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 |
对比计数排序、基数排序和桶排序的测试结果容易看出，这三款时间复杂度为O(n)的排序算法速度相差不大，对一个随机整数序列的排序时，基数排序略占上风。
时间复杂度为O(n)的计数排序、基数排序和桶排序均跟不上时间复杂度为O(nlogn))的快速排序sort的脚步，原因详见本主页基数排序。