如何实现一个通用的、高性能的排序函数？

如何选择合适的排序算法？

如何优化快速排序？

为什么最坏情况下快速排序的时间复杂度是O(n2) 呢？我们前面讲过，如果数据原来就是有序的或者接近有序的，每次分区点都选择最后一个数据，那快速排序算法就会变得非常糟糕，时间复杂度就会退化为O(n2)。实际上，这种O(n2)时间复杂度出现的主要原因还是因为我们分区点选的不够合理。

最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。

这里介绍两个比较常用、比较简单的分区算法，你可以直观地感受一下。

1.三数取中法

我们从区间的首、尾、中间，分别取出一个数，然后对比大小，取这 3 个数的中间值作为分区点。

2.随机法

随机法就是每次从要排序的区间中，随机选择一个元素作为分区点。这种方法并不能保证每次分区点都选的比较好，但是从概率的角度来看，也不大可能会出现每次分区点都选的很差的情况，所以平均情况下，这样选的分区点是比较好的。时间复杂度退化为最糟糕的O(n2)的情况，出现的可能性不大。