前面的三篇文章中，为大家介绍了快速排序的三种划分方法。那么，这里我们想一想，快速排序是否也会有效率低的情况呢？答案是肯定的，快速排序对于数据是敏感的，如果这个数列是非常无序，杂乱无章的，那么快速排序的效率是非常高的，可是如果数列有序，往往快速排序的时间复杂度便由O(nlog2n)退化到O(n ^2)，即相当于冒泡排序。所以，我们需要优化快速排序，这里用到的便是三数取中
即知道这组无序数列的首和尾后，我们便可以求出这个无需数列的中间位置的数，我们只需要在首，中，尾这三个数据中，选择一个排在中间的数据作为基准值，进行快速排序，即可进一步提高快速排序的效率。那么为什么要取中间呢？我们可以假设待排序的数列是一组高度有序的数列，显然首极大可能是最小值，尾极大可能是最大值，此时如果我们选取一个排在中间的值，哪怕是在最坏的情况下，begin和end只需要走到中间位置，那么这个中间值的位置也就确定下来，而不需要begin或end指针要把整个数列遍历一边，从而大大提高快速排序的效率。这种优化方法很简单，只需要在选取基准值之前，执行一边三数取中的函数即可，想必这个函数大家都会写吧。
我们取霍尔划分看一下优化后的代码