4.3.1 初识快速排序
同冒泡排序一样，快速排序也属于交换排序 ，通过元素之间的比较和交换位置来达到排序的目的。
不同的是，冒泡排序在每一轮中只把1个元素冒泡到数列的一端，而快速排序则在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分。
这种思路就叫作分治法 。
每次把数列分成两部分，究竟有什么好处呢？
假如给出一个8个元素的数列，一般情况下，使用冒泡排序需要比较7轮，每一轮把1个元素移动到数列的一端，时间复杂度是O(n 2 )。
而快速排序的流程是什么样子呢？
如图所示，在分治法的思想下，原数列在每一轮都被拆分成两部分，每一部分在下一轮又分别被拆分成两部分，直到不可再分为止。
每一轮的比较和交换，需要把数组全部元素都遍历一遍，时间复杂度是O(n)。这样的遍历一共需要多少轮呢？假如元素个数是n，那么平均情况下需要logn轮，因此快速排序算法总体的平均时间复杂度是O(nlogn) 。
分治法果然神奇！那么基准元素是如何选的呢？又如何把其他元素移动到基准元素的两端？
基准元素的选择，以及元素的交换，都是快速排序的核心问题。让我们先来看看如何选择基准元素。
4.3.2 基准元素的选择
基准元素，英文是pivot，在分治过程中，以基准元素为中心，把其他元素移动到它的左右两边。
那么如何选择基准元素呢？
最简单的方式是选择数列的第1个元素。
这种选择在绝大多数情况下是没有问题的。但是，假如有一个原本逆序的数列，期望排序成顺序数列，那么会出现什么情况呢？
哎呀，整个数列并没有被分成两半，每一轮都只确定了基准元素的位置。
是呀，在这种情况下，数列的第1个元素要么是最小值，要么是最大值，根本无法发挥分治法的优势。
在这种极端情况下，快速排序需要进行n轮，时间复杂度退化成了O(n 2 ) 。
那么，该怎么避免这种情况发生呢？
其实很简单，我们可以随机选择一个元素作为基准元素 ，并且让基准元素和数列首元素交换位置。
这样一来，即使在数列完全逆序的情况下，也可以有效地将数列分成两部分。
当然，即使是随机选择基准元素，也会有极小的几率选到数列的最大值或最小值，同样会影响分治的效果。
所以，虽然快速排序的平均时间复杂度是O(nlogn) ，但最坏情况下的时间复杂度是O(n 2 ) 。
在后文中，为了简化步骤，省去了随机选择基准元素的过程，直接把首元素作为基准元素。
4.3.3 元素的交换
选定了基准元素以后，我们要做的就是把其他元素中小于基准元素的都交换到基准元素一边，大于基准元素的都交换到基准元素另一边。
具体如何实现呢？有两种方法。
1. 双边循环法。
2. 单边循环法。
何谓双边循环法？下面来看一看详细过程。
给出原始数列如下，要求对其从小到大进行排序。
首先，选定基准元素pivot，并且设置两个指针left和right，指向数列的最左和最右两个元素。
接下来进行第1次循环 ，从right指针开始，让指针所指向的元素和基准元素做比较。如果大于或等于 pivot，则指针向左 移动；如果小于 pivot，则right指针停止移动，切换到left 指针。
在当前数列中，1<4，所以right直接停止移动，换到left指针，进行下一步行动。
轮到left指针行动，让指针所指向的元素和基准元素做比较。如果小于或等于 pivot，则指针向右 移动；如果大于 pivot，则left指针停止移动。
由于left开始指向的是基准元素，判断肯定相等，所以left右移1位。
由于7>4，left指针在元素7的位置停下。这时，让left和right指针所指向的元素进行交换。
接下来，进入第2次循环 ，重新切换到right指针，向左移动。right指针先移动到8，8>4，继续左移。由于2<4，停止在2的位置。
按照这个思路，后续步骤如图所示。
大致明白了，那么快速排序怎样用代码来实现呢？
我们来看一下用双边循环法实现的快速排序，代码使用了递归的方式。
1. public static void quickSort(int[] arr, int startIndex,
int endIndex) {
2. // 递归结束条件：startIndex大于或等于endIndex时
3. if (startIndex >= endIndex) {
4. return;
5. }
6. // 得到基准元素位置
7. int pivotIndex = partition(arr, startIndex, endIndex);
8. // 根据基准元素，分成两部分进行递归排序
9. quickSort(arr, startIndex, pivotIndex - 1);
10. quickSort(arr, pivotIndex + 1, endIndex);
11. }
12.
13. /**
14. * 分治（双边循环法）
15. * @param arr 待交换的数组
16. * @param startIndex 起始下标
17. * @param endIndex 结束下标
18. */
19. private static int partition(int[] arr, int startIndex,
int endIndex) {
20. // 取第1个位置（也可以选择随机位置）的元素作为基准元素
21. int pivot = arr[startIndex];
22. int left = startIndex;
23. int right = endIndex;
24.
25. while( left != right) {
26. //控制right 指针比较并左移
27. while(left
28. right--;
29. }
30. //控制left指针比较并右移
31. while( left
32. left++;
33. }
34. //交换left和right 指针所指向的元素
35. if(left
36. int p = arr[left];
37. arr[left] = arr[right];
38. arr[right] = p;
39. }
40. }
41.
42. //pivot 和指针重合点交换
43. arr[startIndex] = arr[left];
44. arr[left] = pivot;
45.
46. return left;
47. }
48.
49. public static void main(String[] args) {
50. int[] arr = new int[] {4,4,6,5,3,2,8,1};
51. quickSort(arr, 0, arr.length-1);
52. System.out.println(Arrays.toString(arr));
53. }
在上述代码中，quickSort方法通过递归的方式，实现了分而治之的思想。
partition方法则实现了元素的交换，让数列中的元素依据自身大小，分别交换到基准元素的左右两边。在这里，我们使用的交换方式是双边循环法。
partition的代码实现好复杂呢，在一个大循环里还嵌套着两个子循环……让我仔细消化消化。
双边循环法的代码确实有些烦琐。除了这种方式，要实现元素的交换也可以利用单边循环法 ，下一节我们来仔细讲一讲。
4.3.4 单边循环法
双边循环法从数组的两边交替遍历元素，虽然更加直观，但是代码实现相对烦琐。而单边循环法则简单得多，只从数组的一边对元素进行遍历和交换。我们来看一看详细过程。
给出原始数列如下，要求对其从小到大进行排序。
开始和双边循环法相似，首先选定基准元素pivot。同时，设置一个mark指针指向数列起始位置，这个mark指针代表小于基准元素的区域边界 。
接下来，从基准元素的下一个位置开始遍历数组。
如果遍历到的元素大于基准元素，就继续往后遍历。
如果遍历到的元素小于基准元素，则需要做两件事：第一，把mark指针右移1位，因为小于pivot的区域边界增大了1；第二，让最新遍历到的元素和mark指针所在位置的元素交换位置，因为最新遍历的元素归属于小于pivot的区域。
首先遍历到元素7，7>4，所以继续遍历。
接下来遍历到的元素是3，3<4，所以mark指针右移1位。
随后，让元素3和mark指针所在位置的元素交换，因为元素3归属于小于pivot的区域。
按照这个思路，继续遍历，后续步骤如图所示。
明白了，这个方法只需要单边循环，确实简单了许多呢！怎么用代码来实现呢？
双边循环法和单边循环法的区别在于partition函数的实现，让我们来看一下代码。
1. public static void quickSort(int[] arr, int startIndex,
int endIndex) {
2. // 递归结束条件：startIndex大于或等于endIndex时
3. if (startIndex >= endIndex) {
4. return;
5. }
6. // 得到基准元素位置
7. int pivotIndex = partition(arr, startIndex, endIndex);
8. // 根据基准元素，分成两部分进行递归排序
9. quickSort(arr, startIndex, pivotIndex - 1);
10. quickSort(arr, pivotIndex + 1, endIndex);
11. }
12.
13. /**
14. * 分治（单边循环法）
15. * @param arr 待交换的数组
16. * @param startIndex 起始下标
17. * @param endIndex 结束下标
18. */
19. private static int partition(int[] arr, int startIndex,
int endIndex) {
20. // 取第1个位置（也可以选择随机位置）的元素作为基准元素
21. int pivot = arr[startIndex];
22. int mark = startIndex;
23.
24. for(int i=startIndex+1; i<=endIndex; i++){
25. if(arr[i]
26. mark ++;
27. int p = arr[mark];
28. arr[mark] = arr[i];
29. arr[i] = p;
30. }
31. }
32.
33. arr[startIndex] = arr[mark];
34. arr[mark] = pivot;
35. return mark;
36. }
37.
38. public static void main(String[] args) {
39. int[] arr = new int[] {4,4,6,5,3,2,8,1};
40. quickSort(arr, 0, arr.length-1);
41. System.out.println(Arrays.toString(arr));
42. }
可以很明显看出，partition方法只要一个大循环就搞定了，的确比双边循环法简单多了。
以上所讲的快速排序实现方法，都是以递归为基础的。其实快速排序也可以基于非递归 的方式来实现。
4.3.5 非递归实现
怎么样用非递归的方式来实现呢？
绝大多数的递归逻辑，都可以用栈 的方式来代替。
为什么这样说呢？
在第1章介绍空间复杂度时我们曾经提到过，代码中一层一层的方法调用，本身就使用了一个方法调用栈。每次进入一个新方法，就相当于入栈；每次有方法返回，就相当于出栈。
所以，可以把原本的递归实现转化成一个栈的实现，在栈中存储每一次方法调用的参数。
下面来看一下具体的代码：
1. public static void quickSort(int[] arr, int startIndex,
int endIndex) {
2. // 用一个集合栈来代替递归的函数栈
3. Stack
Stack
4. // 整个数列的起止下标，以哈希的形式入栈
5. Map rootParam = new HashMap();
6. rootParam.put("startIndex", startIndex);
7. rootParam.put("endIndex", endIndex);
8. quickSortStack.push(rootParam);
9.
10. // 循环结束条件：栈为空时
11. while (!quickSortStack.isEmpty()) {
12. // 栈顶元素出栈，得到起止下标
13. Map
14. // 得到基准元素位置
15. int pivotIndex = partition(arr, param.get("startIndex"),
param.get("endIndex"));
16. // 根据基准元素分成两部分, 把每一部分的起止下标入栈
17. if(param.get("startIndex") < pivotIndex -1){
18. Map
Integer>();
19. leftParam.put("startIndex", param.get("startIndex"));
20. leftParam.put("endIndex", pivotIndex-1);
21. quickSortStack.push(leftParam);
22. }
23. if(pivotIndex + 1 < param.get("endIndex")){
24. Map
Integer>();
25. rightParam.put("startIndex", pivotIndex + 1);
26. rightParam.put("endIndex", param.get("endIndex"));
27. quickSortStack.push(rightParam);
28. }
29. }
30. }
31.
32. /**
33. * 分治（单边循环法）
34. * @param arr 待交换的数组
35. * @param startIndex 起始下标
36. * @param endIndex 结束下标
37. */
38. private static int partition(int[] arr, int startIndex,
int endIndex) {
39. // 取第1个位置（也可以选择随机位置）的元素作为基准元素
40. int pivot = arr[startIndex];
41. int mark = startIndex;
42.
43. for(int i=startIndex+1; i<=endIndex; i++){
44. if(arr[i]
45. mark ++;
46. int p = arr[mark];
47. arr[mark] = arr[i];
48. arr[i] = p;
49. }
50. }
51.
52. arr[startIndex] = arr[mark];
53. arr[mark] = pivot;
54. return mark;
55. }
56.
57. public static void main(String[] args) {
58. int[] arr = new int[] {4,7,6,5,3,2,8,1};
59. quickSort(arr, 0, arr.length-1);
60. System.out.println(Arrays.toString(arr));
61. }
和刚才的递归实现相比，非递归方式代码的变动只发生在quickSort方法中。该方法引入了一个存储Map类型元素的栈，用于存储每一次交换时的起始下标和结束下标。
每一次循环，都会让栈顶元素出栈，通过partition方法进行分治，并且按照基准元素的位置分成左右两部分，左右两部分再分别入栈。当栈为空时，说明排序已经完毕，退出循环。
居然真的实现了非递归方法，好棒！
嘿嘿，快速排序是很重要的算法，与傅里叶变换等算法并称为二十世纪十大算法 。
有关快速排序的知识我们就介绍到这里，希望大家把这个算法吃透，未来会受益无穷！