前面介绍过快速排序算法的实现原理，主要是通过函数的递归调用，将一个序列分成基本有序的两个部分，再对分开的两个部分分部进行一样的区分排序，这样知道整个序列达到有序，那么在实现这个，每一次区分就需要一个枢轴值，前面我们直接使用一个待排序序列或子序列的第一个元素作为枢轴值，这种选择是不科学的，比如我们看看下面一组数：

[java]

int[] array = { 9, 5, 6, 8, 4, 3, 2, 7, 1 };

此时我们选择 int povit = 9,这样一趟排序下来的结果是：

[java]

int[] array = { 1, 5, 6, 8, 4, 3, 2, 7, 9 };

一趟排序：我们发现，只是交换了1和9两个数的位置，这样的效率是不高的，因为我们选取的枢轴值是这个序列中最大的那一个，问题来了，有人说：“如果选取的是这个序列中大小处于中间的那个记录作为枢轴值效率是最高的”，是的，但怎么选取大小处于中间的那个记录呢。当然，如果事先知道顺序，就可定知道了，要是这样，还要排什么序呢，所以这里就是我们要决绝的问题之一，就是怎么样选取一个大小处于整个序列中间或者中间附近的记录呢？

1.枢轴选取的优化：

概率统计学告诉我们，由于序列的随机性，我们也可以采用统计学来解决，因为每一个数处于中间值的概率是相等的，一方面，为了能够选到较靠近中间的，另一方面，又不依赖于序列的长度，即不会造成排序算法的时间复杂度的提升，所以我们可以认为选取几个数，然后比较取中间值，然而这几个数并不能随意取，最好是在序列中的位置有规律，性，通常有两种方法：

三数取中(Median-of-three):取三个关键字先进行排序，将中间数作为枢轴，这三个数是序列的 左，中，右三个位置的记录。

比如刚才那个序列：{ 9, 5, 6, 8, 4, 3, 2, 7, 1 };我们去9,4,1三个数进行比较，然后4作为枢轴记录，这个比9做枢轴记录会更合理。

三数取中的核心优化代码：

[java]

int mid = (low + high) / 2;

//枢轴记录三取一，优化的代码，用于待排序数组元素不是很大的时候

{

if (array[low] > array[high]) {

//交换左端与右端的记录，保证左端较小

swap(low, high, array);

}

if (array[mid] > array[high]) {

//交换中间与右端的记录，保证中间较小

swap(mid, high, array);

}

if (array[mid] > array[low]) {

//交换左端与中间的记录，保证左端较小

swap(mid, low, array);

}

}

int pivotKey = array[low]; // 将三取一后的中间值作为枢轴记录

@用了三个判断，对选取出来三个候选数进行交换排序，然后将中间的那个数赋给pivotKey

整个核心的代码：

[java]

/**

* 优化后快速排序的核心程序,枢轴记录用了三取一，去前中后三个数中间那个

*

* @param low

* @param high

* @param array

* @return 返回枢轴记录

*/

private int partition(int low, int high, int... array) {

int mid = (low + high) / 2;

//枢轴记录三取一，优化的代码，用于待排序数组元素不是很大的时候

{

if (array[low] > array[high]) {

//交换左端与右端的记录，保证左端较小

swap(low, high, array);

}

if (array[mid] > array[high]) {

//交换中间与右端的记录，保证中间较小

swap(mid, high, array);

}

if (array[mid] > array[low]) {

//交换左端与中间的记录，保证左端较小

swap(mid, low, array);

}

}

int pivotKey = array[low]; // 将三取一后的中间值作为枢轴记录

while (low < high) {

while (low < high && array[high] >= pivotKey) {

high--;

}

swap(low, high, array); // 把比枢轴记录小的值交换到低端

while (low < high && array[low] <= pivotKey) {

low++;

}

swap(low, high, array); // 把比枢轴记录大的值交换到高端

}

return low; // 返回枢轴记录的下标

}

@就在原来的基础上加上选取左中右三个记录，并进行排序后去中间的数赋给枢轴记录；

三数取中小结：这种方法的随机性也是挺大的，由于选取的数个数比较小，统计出来的数据也是叫不准确的，一般用于待排序序列个数较小时使用，还有一种是九数取中，这个统计的数据更加准确了，原理是一样的，这里不赘述了；

2.交换的优化：

原始的快速排序算中有这样一段代码，也是核心的代码：

[java]

int pivotKey = array[low]; // 将数组的第一个元素作为枢轴记录

while (low < high) {

while (low < high && array[high] >= pivotKey) {

high--;

}

swap(low, high, array);// 把比枢轴记录小的值交换到低端

while (low < high && array[low] <= pivotKey) {

low++;

}

swap(low, high, array);// 把比枢轴记录大的值交换到高端

}

@上面的代码中，从右端开始，只要有比povitKey值小的记录，就交换左右的值，一趟下来，其实仔细挖掘一下这个交换过程，就知道，这种交换是可以省略的，这里引入一个思路:

每一次将枢轴值用一个标记保存起来，然后在后面的比较中：