快速排序是冒泡排序的一种改进。它的基本思想是通过一趟排序，将要排序的数据分成两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按照此方法对这两部分数据分别进行快速排序。根据描述，整个排序过程完全可以通过递归的方式实现。
快速排序采用了一种分治的策略，通常称为分治法，但是为了便于理解，这里根据 MoreWindows 的说法，将快速排序概括为：挖坑填数 + 分治法。下面通过一个例子来说明这种思想。
有一个初始的数组为：
先设置左右遍历的指针，i = 0，j = 9，取一个基准数（也就是所说的挖坑），这里就取数组第一个数 72。此时 72 已经从数组中挖出了，所以 index = 0 的位置为空。
接下来进行第一趟遍历，首先从右往左比较，将比基准数 72 小的数填到坑里，这里是 48 这个数。
此时 i = 0，j = 8，index = 8 的位置为空。
接着在从左往右比较，将比基准数 72 大的数填到坑里，这里发现是 88 这个数。
此时 i = 3，j = 8，index = 3 的位置为空。
然后继续从右往左比较，将比基准数 72 小的数填到坑里，这里发现是 42 这个数。
此时 i = 3，j = 5，index = 5 的位置为空。
接下来继续从左往右比较，将比基准数 72 大的数填到坑里。当遍历到 i = 5 时，发现左右指针都是 5，这也就意味着在此时这个位置上，左侧所有的数据比右侧的都要小，此时将基准数 72 填到这个坑里，完成第一趟遍历。
接下来还是按照上面的思路，分别对索引区间为 0 ~ 4 和 6 ~ 9 的两部分重复上面的操作。
通过上面的分析，每一趟的算法可以比较容易地写出来。
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
|
static int adjustArray(int[] arr, int l, int r) {
int i = l;
int j = r;
int x = arr[l];
while (i < j) {
while (i < j && arr[j] >= x)
j--;
if (i < j) {
arr[i] = arr[j];
i++;
}
while (i < j && arr[i] < x)
i++;
if (i < j) {
arr[j] = arr[i];
j--;
}
}
arr[i] = x;
return i;
}
|
接下来就可以通过递归实现快排了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
static void quick_sort(int[] arr, int l, int r) {
if (l < r) {
int i = adjustArray(arr, l, r);
quick_sort(arr, l, i - 1);
quick_sort(arr, i + 1, r);
}
}
|
接下来将两部分代码优化合并一下。
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
|
static void quick_sort(int[] arr, int l, int r) {
if (l < r) {
int i = l;
int j = r;
int x = arr[l];
while (i < j) {
while (i < j && arr[j] >= x)
j--;
if (i < j) {
arr[i] = arr[j];
i++;
}
while (i < j && arr[i] < x)
i++;
if (i < j) {
arr[j] = arr[i];
j--;
}
}
arr[i] = x;
quick_sort(arr, l, i - 1);
quick_sort(arr, i + 1, r);
}
}
|
参考
白话经典算法系列之六 快速排序 快速搞定