面试的时候经常被问到这个问题，以至于后来面试官只让我介绍快排，我也一并把快排优化给说了。

方法一：三数取中

取序列中第一个元素、最后一个元素及中间元素，这三个数的中位数作为基准进行序列划分。

方法二：短序列改用插入排序

当待排序序列的长度分割到一定大小后，使用插入排序，因为快速排序会为了极小的子序列而产生许多的函数递归调用，而在短序列排序中插入排序是性能最高的。

方法三：递归过深改用partial_sort

虽然使用了方法一能够避免分割时取到边缘值，但还是可能会取到较边缘的值导致递归层数过深从而降低快排效率。所以我们需要通过方法二的元素个数检验后，再检查分割层次，如果分割层次超过指定值，就改用partial_sort()。关于partial_sort()原理，见 《了解各种与排序有关的选择》 。

方法四：聚集相等元素

针对有大量重复元素的序列进行优化，在一次分割后，可以把与基准点值相等的元素聚集在一起，继续下次分割时，不用再对值相等的元素进行分割。

本文图片均截取自《STL源码剖析》。