谁才是最强的排序算法: 快速排序, 归并排序, 堆排序
谁才是最强的排序算法: 快速排序, 归并排序, 堆排序
知乎上有一个问题是这样的：
堆排序是渐进最优的比较排序算法，达到了O(nlgn)这一下界，而快排有一定的可能性会产生最坏划分，时间复杂度可能为O(n^2)，那为什么快排在实际使用中通常优于堆排序？
昨天刚好写了一篇关于快排优化的文章，今天再多做一个比较吧。首先先看一个排序算法图：
排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
简单选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 稳定 |
直接插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
希尔排序 | O(nlogn)~O(n^2) | O(n^1.3) | O(n^2) | O(1) | 不稳定 |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn)~O(n) | 不稳定 |
可以看到，到达nlogn级别的排序算法，一共有三种，分别是堆排序，归并排序以及快速排序，其中只有归并排序最稳定。那么，为什么要说快速排序的平均情况是最快的呢？
实际上在算法分析中，大O的作用是给出一个规模的下界，而不是增长数量的下界。因此，算法复杂度一样只是说明随着数据量的增加，算法时间代价增长的趋势相同，并不是执行的时间就一样，这里面有很多常量参数的差别，比如在公式里各个排序算法的前面都省略了一个c，这个c对于堆排序来说是100，可能对于快速排序来说就是10，但因为是常数级所以不影响大O。
另外, 堆排比较的几乎都不是相邻元素，对cache极不友好, 数据读取的开销变大。在计算机进行运算的时候，数据不一定会从内存读取出来，而是从一种叫cache的存储单位读取。原因是cache相比内存，读取速度非常快，所以cache会把一部分我们经常读取的数据暂时储存起来，以便下一次读取的时候，可以不必跑到内存去读，而是直接在cache里面找。
一般认为读取数据遵从两个原则：temporal locality，也就是不久前读取过的一个数据，在之后很可能还会被读取一遍；另一个叫spatial locality，也就是说读取一个数据，在它周围内存地址存储的数据也很有可能被读取到。因此，在读取一个单位的数据(比如1个word)之后，不光单个word会被存入cache，与之内存地址相邻的几个word，都会以一个block为单位存入cache中。另外，cache相比内存小得多，当cache满了之后，会将旧的数据剔除，将新的数据覆盖上去。 在进行堆排序的过程中，由于我们要比较一个数组前一半和后一半的数字的大小，而当数组比较长的时候，这前一半和后一半的数据相隔比较远，这就导致了经常在cache里面找不到要读取的数据，需要从内存中读出来，而当cache满了之后，以前读取的数据又要被剔除。 简而言之快排和堆排读取arr[i]这个元素的平均时间是不一样的。
即使是同样的算法，不同的人写的代码，不同的应用场景下执行时间也可能差别很大。下面是一个测试数据：
- 测试的平均排序时间：数据是随机整数，时间单位是s
- 数据规模 快速排序 归并排序 希尔排序 堆排序
- 1000万 0.75 1.22 1.77 3.57
- 5000万 3.78 6.29 9.48 26.54
- 1亿 7.65 13.06 18.79 61.31
堆排序每次取一个最大值和堆底部的数据交换，重新筛选堆，把堆顶的X调整到位，有很大可能是依旧调整到堆的底部（堆的底部X显然是比较小的数，才会在底部），然后再次和堆顶最大值交换，再调整下来，可以说堆排序做了许多无用功。
总结起来就是，快排的最坏时间虽然复杂度高，但是在统计意义上，这种数据出现的概率极小，而堆排序过程里的交换跟快排过程里的交换虽然都是常量时间，但是常量时间差很多。