排序之快速排序(下)
快速排序优化
快排上是可以进行优化的，那么可以进行哪些优化了，是不是和你想的一样了？ 我们往下看
1、优化枢纽值的选取
如果我们选取的pivotKey是处于整个序列的中间位置，那么我们可以将整个序列分成小数集合和大数集合了。但注意，我刚才说的是“如果……是中间”， 那么假如我们选取的pivotkey不是中间数如何呢？比如我们用到的数组{9,1,5,8,3,7,4,6,2}，由代码“pivotkey=arr[low];”知道，我们应该选取9作为第一个枢轴pivotKey。此时，经过一轮 “pivot=partition(arr,1,9);”转换后，它只是更换了9与2的位置，并且返回9给pivot，整个系列并没有实质性的变化。
就是说，代码“pivotkey=arr[low];”变成了一个潜在的性能瓶颈。排序速度的快慢取决于arr[low]的关键字处在整个序列 的位置，arr[low]太小或者太大，都会影响性能(比如第一例子中的5就是一个中间数，而第二例子的9就是一个相对整个序列过大的数)。因为在现实中， 待排序的系列极有可能是基本有序的，此时，总是固定选取第一个关键字（其实无论是固定选取哪一个位置的关键字）作为首个枢轴就变成了极为不合理的作法。 改进办法，有人提出，应该随机获得一个low与high之间的数rnd，让它的关键字arr[rnd]与arr[low]交换，此时就不容易出现这样的情况。这被称为随机选取枢轴法。应该说，这在某种程度上，解决了对于基本有序的序列快速排序时的性能瓶颈。不过，随机就有些撞大运的感觉，万一没撞成功，随机到了依然是很小或很大的关键字怎么办呢？ 再改进，于是就有了三数取中（median-of-three）法。即取三个关键字先进行排序，将中间数作为枢轴，一般是取左端、右端和中间三个数， 也可以随机选取。这样至少这个中间数一定不会是最小或者最大的数，从概率来说，取三个数均为最小或最大数的可能性是微乎其微的，因此中间数位于较为中间的 值的可能性就大大提高了。由于整个序列是无序状态，随机选取三个数和从左中右端取三个数其实是一回事，而且随机数生成器本身还会带来时间上的开销，因此随机生成不予考虑。 我们来看看取左端、右端和中间三个数的实现代码，我们来看看新的partition方法。
/**
* 寻找枢纽值的下标，并返回
* 交换arr[low...high]中的元素，移动枢纽值到正确的位置
* @param arr
* @param low
* @param high
* @return
*/
private static int partition(int[] arr, int low, int high) {
//从第一、中间、最后三个元素中选取第二大的
int m = low + (high-low)/2;
if (arr[low] > arr[high]){
swap(arr,low,high); /* 交换左端与右端数据，保证左端较小 */
}
if (arr[m] > arr[high]){
swap(arr,high,m); /* 交换中间与右端数据，保证中间较小 */
}
if (arr[m] > arr[low]){
swap(arr,m,low); /* 交换中间与左端数据，保证左端较小 */
}
int pivotValue = arr[low]; // 选取arr[low]当作枢纽值
// 从两端向中间扫描，使枢纽值移动到正确的位置
while(low < high){
while(low<high && arr[high]>=pivotValue){
high --;
}
swap(arr,low,high); // 将比枢纽值小的记录交换到低端
while(low<high && arr[low]<=pivotValue){
low ++;
}
swap(arr,low,high); // 将比枢纽值大的记录交换到高端
}
return low;
}这样就保障枢纽值就有一定的合理性了，当然，如果数列特别大的话，可以进行九数取中（median-of-nine），它是先从数组中分三次取样，每次取三个数，三个样品各取出中数，然后从这三个中数当中再取出一个中数作为枢轴。
2、优化不必要的交换
直接上代码
/**
* 寻找枢纽值的下标，并返回
* 交换arr[low...high]中的元素，移动枢纽值到正确的位置
* @param arr
* @param low
* @param high
* @return
*/
private static int partition(int[] arr, int low, int high) {
//从第一、中间、最后三个元素中选取第二大的
int m = low + (high-low)/2;
if (arr[low] > arr[high]){
swap(arr,low,high); /* 交换左端与右端数据，保证左端较小 */
}
if (arr[m] > arr[high]){
swap(arr,high,m); /* 交换中间与右端数据，保证中间较小 */
}
if (arr[m] > arr[low]){
swap(arr,m,low); /* 交换中间与左端数据，保证左端较小 */
}
int pivotValue = arr[low]; // 选取arr[low]当作枢纽值
// 从两端向中间扫描，使枢纽值移动到正确的位置
while(low < high){
while(low<high && arr[high]>=pivotValue){
high --;
}
arr[low] = arr[high]; // 将比枢纽值小的记录交换到低端
while(low<high && arr[low]<=pivotValue){
low ++;
}
arr[high]=arr[low]; // 将比枢纽值大的记录交换到高端
}
arr[low] = pivotValue;
return low;
}3、优化小序列时的排序方案
如果数组非常小，其实快速排序反而不如直接插入排序来得更好（直接插入是简单排序中性能最好）。其原因在于快速排序用到了递归操作，在大量数据排序时，这点性能影响相对于它的整体算法优势而言是可以忽略的，但如果数组只有几个记录需要排序时，用快速排序效率反而更低，需要改进下qSort方法。
/**
* 对序列arr中的子序列arr[low..high]作快速排序
* @param arr
* @param low
* @param high
*/
private static void qSort(int[] arr, int low, int high) {
int pivotKey;
if(high-low > 7){
// 找到枢纽值的位置，此时arr[low,pivotKey-1]都小于(大于)arr[pivotKey],arr[pivotKey+1...high]都大于(小于)arr[pivotKey]
pivotKey = partition(arr,low,high);
qSort(arr,low,pivotKey-1); // 对arr[low...pivotKey-1]进行快速排序
qSort(arr,pivotKey+1,high); // 对arr[pivotKey+1...high]进行快速排序
} else {
strainghtInsertSort(arr,low,high);
}
}
/**
* 对序列arr[low...high]a进行直接插入排序
* @param arr
* @param low
* @param high
*/
private static void strainghtInsertSort(int[] arr, int low, int high) {
for(int i=low+1; i<=high; i++){ // 将arr[i]插入到有序列表
for(int j=i-1; j>=0&&arr[j]>arr[j+1]; j--){ // arr[low...j]是有序列表
swap(arr,j,j+1);
}
}
}等等，还可以进行其他方面的优化的，更多的优化就交给各位了!