参考书目：《大话数据结构》
一：快速排序
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;
}
}