[toc]
如何选择合适的排序算法？
线性排序算法的时间复杂度比较低，适用场景比较特殊。所以如果要写一个通用的排序函数，不能选择线性排序算法。
时间复杂度是 O(nlogn) 的排序算法不止一个，已经讲过的有归并排序、快速排序，后面讲堆的时候还会讲到堆排序。堆排序和快速排序都有比较多的应用，比如 Java 语言采用堆排序实现排序函数，C 语言使用快速排序实现排序函数。
使用归并排序的情况其实并不多，因为归并排序并不是原地排序算法，空间复杂度是 O(n)。
如何优化快速排序？
最坏情况下快速排序的时间复杂度是 O(n^2^)，出现的主要原因是因为分区点选的不够合理。
最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。
三数取中法
从区间的首、尾、中间，分别取出一个数，然后对比大小，取这 3 个数的中间值作为分区点。这样每间隔某个固定的长度，取数据出来比较，将中间值作为分区点的分区算法，肯定要比单纯取某一个数据更好。但是，如果要排序的数组比较大，那“三数取中”可能就不够了，可能要“五数取中”或者“十数取中”。
随机法
随机法就是每次从要排序的区间中，随机选择一个元素作为分区点。这种方法并不能保证每次分区点都选的比较好，但是从概率的角度来看，也不大可能会出现每次分区点都选的很差的情况，所以平均情况下，这样选的分区点是比较好的。时间复杂度退化为最糟糕的 O(n2) 的情况，出现的可能性不大。
举例分析排序函数
O(n^2^) 时间复杂度的算法并不一定比 O(nlogn) 的算法执行时间长
O(nlogn) 在没有省略低阶、系数、常数之前可能是 O(knlogn + c)，而且 k 和 c 有可能还是一个比较大的数。假设 k=1000，c=200，当我们对小规模数据（比如 n=100）排序时，n2的值实际上比 knlogn+c 还要小。
knlogn+c = 1000 100 log100 + 200 远大于 10000
n^2 = 100*100 = 10000
对于小规模数据的排序，O(n2) 的排序算法并不一定比 O(nlogn) 排序算法执行的时间长。对于小数据量的排序，我们选择比较简单、不需要递归的插入排序算法。