参考书目:《大话数据结构》
一:快速排序
1.基本思想:通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。
2.核心问题:枢轴的获取。选取一个关键字,通过调整使得它左边的值都比它小,右边的值都比它大,则这样的关键字称为枢轴值(pivotkey),通过获取枢轴的下标,从而在接下来的对子序列的再次快排明确界限。
二:快速排序(普通版)
1.代码:
public class QuickSort {
public static void sort(int[] a) {
int n = a.length - 1;
QSort(a, 1, n);
}
private static void QSort(int[] a, int low, int high) {
int pivot; // 枢轴的下标,将某个数放在此位置,使得它左边的值都比它小,右边的都比它大
if (low < high) {
pivot = Partition(a, low, high); // 将a[low..high]一分为二,算出枢轴下标pivot
QSort(a, low, pivot - 1); // 对低子表递归排序
QSort(a, pivot + 1, high); // 对高子表递归排序
}
}
// 交换顺序表a中子表的记录,使枢轴记录到为,并返回其位置
private static int Partition(int[] a, int low, int high) {
int pivotkey = a[low]; // 用子表的第一个记录作枢轴记录
while (low < high) { // 从表的两端交替向中间扫描
while (low < high && a[high] >= pivotkey) {
high--;
}
swap(a, low, high); // 将比枢轴值小的记录交换到低端
while (low < high && a[low] <= pivotkey) {
low++;
}
swap(a, low, high); // 将比枢轴值大的记录交换到高端
}
return low; // 最终low == high,所有返回枢轴所在位置
}
private static void swap(int[] a, int x, int y) {
int temp;
temp = a[x];
a[x] = a[y];
a[y] = temp;
}
}
2.缺陷:
(1)枢轴的选取:如果选取的pivotkey是处于整个序列的中间位置,那么可用将整个序列分成小数集合和大数集合,但如果选取的pivotkey不是中间位置的数,则整个序列在一次QSort()后并没有实质性的变化,进而影响性能。
(2)交换操作:多次交换完全可以用一个哨兵与替换代替,而且交换操作也影响了性能。
(3)小数组排序:对于少量记录的序列,快排显得大材小用,不如直接用更合适的直接插入排序。
(4)递归操作:如果待排序序列划分极端不平衡,递归的深度将趋近于n,而不是平衡时的log2n,因栈的大小是很有限的,每次递归都会耗费一定的栈空间,函数参数越多,每次递归耗费的空间也越大,若减少递归,性能将大大提高。
二:快速排序(优化版)
1.优化方案:
(1)优化选取枢轴(三数取中),选取更较为合适的枢轴值,使得左小右大更均匀;
(2)优化交换操作为替换,分析得知,swap交换操作本身不必要;
(3)优化小数组时的排序方案为直接插入排序,而对于大数组则采用快排;
(4)优化递归操作,将对高子表的递归转为只对低子表的迭代版递归
2.改进后的代码:
(注:考虑侧重点问题,直接插入排序算法的代码不再给出)
public class QuickSortUp {
// 1.优化选取枢轴(三数取中),选取更较为合适的枢轴值,使得左小右大更均匀;
// 2.优化交换操作为替换,分析得知,swap交换操作本身不必要;
// 3.优化小数组时的排序方案为直接插入排序,而对于大数组则采用快排;
// 4.优化递归操作,将对高子表的递归转为只对低子表的迭代版递归
public static void sort(int[] a) {
int n = a.length - 1;
QSort(a, 1, n);
}
private static void QSort(int[] a, int low, int high) {
int ORDINARY_LEN = 7; // 数组长度阈值,当小于时,可用直接插入排序
int pivot; // 枢轴的下标,将某个数放在此位置,使得它左边的值都比它小,右边的都比它大
if ((high - low) > ORDINARY_LEN) {
while(low < high) {
pivot = Partition(a, low, high); // 将a[low..high]一分为二,算出枢轴下标pivot
QSort(a, low, pivot - 1); // 对低子表递归排序
low = pivot + 1; // 尾递归
}
} else {
InterSort.sort(a);
}
}
// 交换顺序表a中子表的记录,使枢轴记录到为,并返回其位置
private static int Partition(int[] a, int low, int high) {
int pivotkey;
int m = low + (high - low) / 2;
if(a[low] > a[high]) {
swap(a, low, high);
}
if(a[m] > a[high]) {
swap(a, high, m);
}
if(a[m] > a[low]) {
swap(a, m, low);
}
pivotkey = a[low]; // 此时a[low]为三数取中得到的中间值
a[0] = pivotkey; // 哨兵
while (low < high) { // 从表的两端交替向中间扫描
while (low < high && a[high] >= pivotkey) {
high--;
}
a[low] = a[high]; //改交换为替换
while (low < high && a[low] <= pivotkey) {
low++;
}
a[high] = a[low];
}
a[low] = a[0];
return low; // 最终low == high,所有返回枢轴所在位置
}
private static void swap(int[] a, int x, int y) {
int temp;
temp = a[x];
a[x] = a[y];
a[y] = temp;
}
}