快速排序（Quick Sort）
快速排序是由东尼・霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 $O (n\log n)$ 次比较。在最坏状况下则需要 $O (n^2)$ 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 $O (n\log n)$ 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序的最坏运行情况是 $O (n^2)$，比如说顺序数列的快排。但它的平摊期望时间是 $O (n\log n)$，且 $O (n\log n)$ 记号中隐含的常数因子很小，比复杂度稳定等于 $O (n\log n)$ 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
快速排序（Quick Sort）的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
- 从数列中挑出一个元素，称为 “基准”（
pivot）； - 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
动图演示
快速排序一般有两种写法，挖坑法和交换法，两者有一点区别，但总体都是基于分治思想的，上图是交换法的动图演示。
挖坑法
挖坑法的思想： 用两个指针 i 和 j 分别指向数组的第一个数和最后一个数，即令 i = 0，j = arr.length - 1。选取第一个数为基准数（可以选任意一个数为基准数，习惯选第一个）pivot = arr [0]，首先从 j 所指位置自右向左逐一搜索，找到第一个小于 pivot 的数字，将其存入 i 所指的位置，并令 i = i + 1。然后再从 i 所指位置起自左向右逐一搜索，找到第一个大于 pivot 的数字，将其存入 j 所指的位置，并令 j = j - 1。重复上述过程，直至 i == j 为止，此时令 arr [i] = pivot，至此一次分区完成。
挖坑法，顾名思义就是排序的过程要挖坑。以图中所示数组为例，取第一个数为基准数。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $\color {red}{3}$ | 44 | 38 | 5 | 47 | 15 | 36 | 26 | 27 | 2 | 46 | 4 | 19 | 50 | 48 |
初始时，i = 0; j = 14; pivot = arr [i] = 3。
由于已经将 arr [0] 中的数保存到 pivot 中，可以理解成在数组 arr [0] 上挖了个坑，可以将其它数据填充到这来。
从 j 开始向前找一个比 pivot 小，当 j = 9 时，符合条件，将 arr [9] 挖出再填到上一个坑 arr [0] 中：arr [0] = arr [9]; i++; 这样一个坑 arr [0] 就被填上了，但又形成了一个新坑 arr [9]，需要找新的数字填 arr [9] 这个坑。这次从 i 开始向后找一个大于 pivot 的数，当 i = 1 时，符合条件，将 arr [1] 挖出再填到上一个坑中：arr [9] = arr [1]; j--;
数组变为：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2 | 44 | 38 | 5 | 47 | 15 | 36 | 26 | 27 | 44 | 46 | 4 | 19 | 50 | 48 |
再重复上面的步骤，先从后向前找，再从前向后找，最后发现，i 和 j 重合了，此时，i = j = 1，令 arr [i] = pivot，一次分区完成。
数组变为：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2 | $\color {red}{3}$ | 38 | 5 | 47 | 15 | 36 | 26 | 27 | 44 | 46 | 4 | 19 | 50 | 48 |
此时，arr [1] 前面的数字都小于它，后面的数字都大于它。再次对分区后的子区间重复上述步骤即可。
Java 实现 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47/**
* 快速排序，挖坑法
*/
public static int[] quickSort1 (int[] arr) {
partition1 (arr, 0, arr.length - 1);
return arr;
}
static void partition1(int arr [], int left, int right) {
if (left > right) {
return;
}
//pivot 为基准值，arr [left] 赋值给 pivot 后，空出来相当于挖了个坑
int pivot = arr [left];
int i = left, j = right;
while (i < j) {
// 找到小于基准值的 arr [j]
while (i < j && arr [j] >= pivot) {
j--;
}
if (i < j) {
// 挖坑，arr [j] 空出来，相当于挖了个坑
// 也可以理解为 arr [i] 挖的坑 arr [j] 填上
// 第一次循环时，i = 0，就是基准值所在地
// 所以第一个被填上的坑一定是在基准值处挖的坑
arr [i] = arr [j];
i++;
}
// 找到大于基准值的 arr [i]
while (i < j && arr [i] <= pivot) {
i++;
}
if (i < j) {
// 填坑，arr [j] 挖的坑，arr [i] 填上
// 也可以理解为 arr [i] 挖了一个坑
arr [j] = arr [i];
j--;
}
}
//i 和 j 相等时，将基准值填到 arr [i]
// 这时 arr [i] 左边的数字都比它小，右边的数字都比它大
arr [i] = pivot;
// 递归处理左半数组
partition1 (arr, left, i - 1);
// 递归处理右半数组
partition1 (arr, i + 1, right);
}
交换法
交换法的思想： 用两个指针 i 和 j 分别指向数组的第一个数和最后一个数，选取第一个数为基准数 pivot = arr [0]，首先从 j 所指位置自右向左逐一搜索，找到第一个小于 pivot 的数字，再从 i 所指位置自左向右逐一搜索，找到第一个大于 pivot 的数字，如果此时 i < j，则交换 i 和 j 所指的两个数字，然后继续以上搜索，满足条件时交换，直至 i == j 为止，最后将基准值位置的数字（基准值）与 i, j 相等时所指位置的数字交换，至此一次分区结束。
Java 实现 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39/**
* 快速排序，交换法
*/
public static int[] quickSort2 (int[] arr) {
partition2 (arr, 0, arr.length - 1);
return arr;
}
static void partition2(int[] arr, int left, int right) {
if (left < right) {
return;
}
// 基准值
int pivot = arr [left];
int i = left, j = right, temp;
while (i < j) {
// 找到小于基准值的 arr [j]
while (i < j && arr [j] >= pivot) {
j--;
}
// 找到大于基准值的 arr [i]
while (i < j && arr [i] <= pivot) {
i++;
}
// 大于基准值的 arr [i] 和小于基准值的 arr [j] 交换
if (i < j) {
temp = arr [i];
arr [i] = arr [j];
arr [j] = temp;
}
}
// 最后将基准值位置的数字（基准值）与 i,j 相等位置的数字交换
arr [left] = arr [i];
arr [i] = pivot;
// 递归处理左半数组
partition2 (arr, left, i - 1);
// 递归处理右半数组
partition2 (arr, i + 1, right);
}
参考文献
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/6.quickSort.md
https://blog.csdn.net/morewindows/article/details/6709644