版权声明：本文源自简书tianma，转载请务必注明出处：http://www.jianshu.com/p/df8a9e136295
概念
快速排序是交换类排序，采用分治思想，其基本原理是：通过一趟排序，将待排序数组分割成独立的两部分，其中一部分的关键字均比另一部分小；然后再分别对这两部分序列递归进行快速排序，从而使整个序列有序。
具体算法步骤：
- 在待排序的记录序列中选取一个记录作为枢轴(pivot)；
- 通过一趟排序，将所有小于枢轴的记录都移到枢轴的左边，将所有大于枢轴的记录都移到枢轴的右边，其实就是将当前待排序序列分为两部分，左边部分的记录均小于右边部分的记录，这样的操作叫做partition(分割)，分割操作结束后，枢轴所处的位置就是最终排序后它所处的位置；
- 对枢轴左右两边的子序列重复步骤1和2，直至所有子记录序列只剩下一个记录为止。
以上步骤中，关键点是 1. 枢轴(pivot)的选取方式； 2. 对分割操作(partition)的细节处理。
未优化的快速排序
- 枢轴的选取：将待排序序列的第1个记录作为枢轴；
- 分割操作 ： 分割操作中使用到了交换；
Java实现
// 定义接口
interface Sorter {
/**
* 将数组按升序排序
*/
int[] sort(int[] arr);
/**
* 交换数组arr中的第i个位置和第j个位置的关键字
*/
default void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
// 未优化的快速排序
class QuickSorter implements Sorter {
@Override
public int[] sort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
return arr;
}
/**
* 对数组arr[low...high]的子序列作快速排序，使之有序
*/
protected void quickSort(int[] arr, int low, int high) {
int pivotLoc; // 记录枢轴(pivot)所在位置
if (low < high) {
pivotLoc = partition(arr, low, high); // 将arr[low...high]一分为二,并返回枢轴位置
quickSort(arr, low, pivotLoc - 1);// 递归遍历arr[low...pivotLoc-1]
quickSort(arr, pivotLoc + 1, high); // 递归遍历arr[pivotLoc+1...high]
}
}
/**
* 在arr[low...high]选定pivot=arr[low]作为枢轴（中间位置），将arr[low...high]分成两部分，
* 前半部分的子序列的记录均小于pivot，后半部分的记录均大于pivot;最后返回pivot的位置
*/
protected int partition(int[] arr, int low, int high) {
int pivot;
pivot = arr[low]; // 将arr[low]作为枢轴
while (low < high) { // 从数组的两端向中间扫描 // A
while (low < high && arr[high] >= pivot) { // B
high--;
}
swap(arr, low, high); // 将比枢轴pivot小的元素交换到低位 // C
while (low < high && arr[low] <= pivot) { //D
low++;
}
swap(arr, low, high); // 将比枢轴pivot大的元素交换到高位 // E
}
return low; // 返回一趟下来后枢轴pivot所在的位置
}
}
演示
为了方便演示，我对上面代码中的分割操作partition方法的代码进行了标注（分别标注为 A,B,C,D,E）。
对于待排序序列 {5, 1, 9, 3, 7, 4, 8, 6, 2}，我们来演示其第一趟排序过程：
low = 0, high = 8, pivot = arr[low] = 5;
- A处，low = 0, high = 8, low<high，进行A循环；
- B处，high的值不断递减，直至arr[high] = 2 小于pivot，跳出B循环：
pivot
↓
5 1 9 3 7 4 8 6 2
↑ ↑
low high
- C处，执行low和high的元素交换：
pivot
↓
2 1 9 3 7 4 8 6 5
↑ ↑
low high
- D处，low的值不断递增，直至arr[low] = 9 大于 pivot，跳出D循环:
pivot
↓
2 1 9 3 7 4 8 6 5
↑ ↑
low high
- E处，执行low和high的元素交换：
pivot
↓
2 1 5 3 7 4 8 6 9
↑ ↑
low high
- A处，low =2, high = 8, low < high，继续循环A；
- B处，high的值不断递减，直至arr[high] = 4 小于pivot，跳出B循环：
pivot
↓
2 1 5 3 7 4 8 6 9
↑ ↑
low high
- C处，执行low和high的元素交换：
pivot
↓
2 1 4 3 7 5 8 6 9
↑ ↑
low high
- D处，low的值不断递增，直至arr[low] = 7 大于 pivot，跳出D循环：
pivot
↓
2 1 4 3 7 5 8 6 9
↑ ↑
low high
- E处，执行low和high的元素交换：
pivot
↓
2 1 4 3 5 7 8 6 9
↑ ↑
low high
- A处，low = 4， high = 5， low < high， 继续循环A：
- B处，high不断递减，直至high=4 等于 low，不满足 low < high，跳出B循环：
pivot
↓
2 1 4 3 5 7 8 6 9
↑
low
high
- 因为low和high已经重合，所以在接下来的C、D、E操作中序列均未发生变化
- A处，low=4, high = 4, 不满足 low < high, 跳出A循环，最后返回low=4，即为pivot所在位置；
所以第1趟排序下来之后，序列会变成 {2, 1, 4, 3, 5, 7, 8, 6, 9}；然后再对子序列{2, 1, 4, 3} 和 {7, 8, 6, 9} 做同样的操作即可完成整个排序。
对于partition方法中的low和high，可以这样理解：在low左边的记录都都小于等于枢轴pivot，在high右边的记录都大于等于枢轴pivot，那么当low和high重合时，则表示已经分割完毕，重合的位置（即low的值）就是枢轴pivot的位置。
快速排序的优化
(1) 枢轴的选取方式的优化：
枢轴的选取方式有：(1) 固定位置选取；(2) 随机位置选取； (3) 三值取中法 等
固定位置选取：选取当前序列的第一个元素或者最后一个元素作为枢轴，上面的算法的枢轴选取方式即为固定位置选取。该方法不是一个好的选取方案，因为当整个序列有序时，每次分割(partition)操作只会将待排序序列减1，此时为最坏情况，算法复杂度沦为O(n^2)。然而，在待排序的序列中局部有序是相当常见的，所以固定位置选取枢轴不是一种好的选择。
随机位置选取：随机选取当前待排序序列的任意记录作为枢轴。由于采取随机，所以时间性能要强于固定位置选取。
三值取中法： 待排序序列的前(第一个位置)、中(中间位置)、后(最后一个位置)三个记录中的中间值(按大小排序)作为枢轴，比如:
9 1 7 5 2 8 6 3 4
↑ ↑ ↑
low mid high
前 中 后
由于 9 > 4 > 2； 因此将4作为此次分割(partition)操作的枢轴。
三值取中操作后，整个序列变为：
4 1 7 5 2 8 6 3 9
↑ ↑ ↑
low mid high
前 中 后
三值取中本质上就是随机位置选取，但是由于随机位置选取过程中需要用到随机种子来产生随机数，而三值取中不需要，所以三值取中要优于随机位置选取。
所以优化枢轴的选取方式时，我们选择三值取中的方式。
(2) 优化小数组时的排序方案：
当局部排序数组长度较小时，采用插入排序，而非快速排序，因为长度分割到够小后，继续分割的效率要低于直接插入排序。
(3) 略去不必要的交换：
略去不必要的交换，将交换操作改为替换操作。
因为交换操作需要进行3次赋值操作，而替换操作只需要进行1次赋值操作。
Java实现
// 优化的快速排序
class OptimizedQuickSorter extends QuickSorter {
/**
* 插入排序最大数组长度值
*/
private static final int MAX_LENGTH_INSERT_SORT = 7;
/**
* 对数组arr[low...high]的子序列作快速排序，使之有序
*/
@Override
protected void quickSort(int[] arr, int low, int high) {
int pivotLoc; // 记录枢轴(pivot)所在位置
if ((high - low + 1) > MAX_LENGTH_INSERT_SORT) {
// 待排序数组长度大于临界值，则进行快速排序
pivotLoc = partition(arr, low, high); // 将arr[low...high]一分为二,并返回枢轴位置
quickSort(arr, low, pivotLoc - 1);// 递归遍历arr[low...pivotLoc-1]
quickSort(arr, pivotLoc + 1, high); // 递归遍历arr[pivotLoc+1...high]
} else {
// 2. 优化小数组时的排序方案，将快速排序改为插入排序
insertSort(arr, low, high); // 对arr[low...high]子序列进行插入排序
}
}
/**
* 在arr[low...high]中利用三值取中选取枢轴(pivot)，将arr[low...high]分成两部分，
* 前半部分的子序列的记录均小于pivot，后半部分的记录均大于pivot;最后返回pivot的位置
*/
@Override
protected int partition(int[] arr, int low, int high) {
int pivot;
pivot = medianOfThree(arr, low, high); // 1. 优化排序基准，使用三值取中获取中值
while (low < high) { // 从数组的两端向中间扫描 // A
while (low < high && arr[high] >= pivot) { // B
high--;
}
// swap(arr, low, high); // 将比枢轴pivot小的元素交换到低位
arr[low] = arr[high]; // 3. 优化不必要的交换，使用替换而不是交换 // C
while (low < high && arr[low] <= pivot) { // D
low++;
}
// swap(arr, low, high); // 将比枢轴pivot大的元素交换到高位
arr[high] = arr[low]; // 3. 优化不必要的交换，使用替换而不是交换 // E
}
arr[low] = pivot; // F
return low; // 返回一趟下来后枢轴pivot所在的位置
}
/**
* 通过三值取中(从arr[low...high]子序列中)获取枢轴pivot的值，让arr[low]变成中值;并返回计算的枢轴(pivot)
*/
private int medianOfThree(int[] arr, int low, int high) {
int mid = low + ((high - low) >> 1); // mid = low + (high-low)/2, 中间元素下标
// 使用三值取中得到枢轴
if (arr[low] > arr[high]) { // 目的：让arr[low] <= arr[high]
swap(arr, low, high);
}
if (arr[mid] > arr[high]) { // 目的：让arr[mid] <= arr[high]
swap(arr, mid, high);
}
if (arr[mid] > arr[low]) { // 目的： 让arr[low] >= arr[mid]
swap(arr, low, mid);
}
// 经过上述变化，最终 arr[mid]<=arr[low]<=arr[high]，则arr[low]为中间值
return arr[low];
}
/**
* 对子序列arr[low...high]进行插入排序
*/
private void insertSort(int[] arr, int low, int high) {
int i, j;
int tmp;
for (i = low + 1; i <= high; i++) { // 从下标low+1开始遍历,因为下标为low的已经排好序
if (arr[i] < arr[i - 1]) {
// 如果当前下标对应的记录小于前一位记录,则需要插入,否则不需要插入，直接将记录数增加1
tmp = arr[i]; // 记录下标i对应的元素
for (j = i - 1; j >= low && arr[j] > tmp; j--) {
arr[j + 1] = arr[j]; // 记录后移
}
arr[j + 1] = tmp; // 插入正确位置
}
}
}
}
演示
为了方便演示，我对上面代码中的分割操作partition方法的代码仍然进行了标注（分别标注为 A,B,C,D,E,F）。
对于待排序序列 {5, 1, 9, 3, 7, 4, 8, 6, 2}，我们来演示其第一趟排序过程：
low = 0， high = 8， high-low+1=9 > MAX_LENGTH_INSERT_SORT， 所以需要进行快速排序，接下来进行分割(partition)操作；
- 此时待排序序列：
5 1 9 3 7 4 8 6 2
↑ ↑
low high
- 三值取中前：
5 1 9 3 7 4 8 6 2
↑ ↑ ↑
low mid high
三值取中后：
pivot
↓
5 1 9 3 2 4 8 6 7
↑ ↑ ↑
low mid high
pivot = 5；
- A处，low = 0, high = 8, low < high, 进行A循环；
- B处，high的值不断递减，直至arr[high] = 4 小于pivot，跳出B循环：
5 1 9 3 2 4 8 6 7
↑ ↑
low high
- C处，arr[low] = arr[high]，将低位的值替换成高位的值：
4 1 9 3 2 4 8 6 7
↑ ↑
low high
- D处，low的值不断递增，直至arr[low] = 9 大于 pivot，跳出D循环:
4 1 9 3 2 4 8 6 7
↑ ↑
low high
- E处，arr[high] = arr[low]， 将高位的值替换成低位的值：
4 1 9 3 2 9 8 6 7
↑ ↑
low high
- A处，low = 2, high = 5, low < high, 进行A循环；
- B处，high的值不断递减，直至arr[high] = 2 小于pivot，跳出B循环：
4 1 9 3 2 9 8 6 7
↑ ↑
low high
- C处，arr[low] = arr[high]，将低位的值替换成高位的值：
4 1 2 3 2 9 8 6 7
↑ ↑
low high
- D处，low的值不断递增，直至low = 4, high = 4, low == high，不满足 low<high，跳出D循环:
4 1 2 3 2 9 8 6 7
↑
low
high
- 因为low和high已经重合，所以在接下来的E操作中序列未发生变化；
- A处，low=4, high = 4, 不满足 low < high, 跳出A循环；
- F处， arr[low] = pivot:
4 1 2 3 5 9 8 6 7
↑
low
high
- 最后返回low = 4，即为pivot所在的位置。
所以这趟排序下来之后，序列会变成 {4 1 2 3 5 9 8 6 7}；然后再对子序列{4, 1, 2, 3} 和 {9, 8, 6, 7} 做同样的操作即可完成整个排序。
复杂度
时间复杂度：
时间复杂度为O(nlogn)，在对快速排序进行各种细节性的优化后，快速排序的性能大大提高，在一般条件下超越了其它排序方法，故得此名。
空间复杂度：
就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归的深度为log2n，其空间复杂度也就为O(logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。
参考链接：
常见排序算法 - 快速排序 (Quick Sort)
三种快速排序以及快速排序的优化
