一、什么是快速排序
快速排序同冒泡排序一样，是一种
交换排序，通过元素之间的比较和交换达到排序目的。不同的是，冒泡排序每一轮只把一个元素（该轮最大/最小）冒泡到最右端；而快速排序每一轮则是选一个
基准元素（ pivot），并让其它
比基准元素小的数通过交换放在基准元素
左端，而
比基准元素大的数则放在基准元素的
右端，从而把待排序的数列拆分成两部分，这就是
分治法的典型应用。然后不断重复这个过程（
递归），待排序的序列就变成了有序序列。
二、基准元素的选择
通过上述对快速排序思想的了解，可以发现：基准元素的选择很重要。一般情况下，基准元素
最简单的就是
选择序列的第一个元素，但是如果待排序的序列是一个
逆序序列，期望排序成一个顺序序列，每一轮排序选择第一个元素作为基准元素，会出现什么情况呢？如下图：
**从上图中可以看出：**在这种情况下，
每一轮排序只会确定基准元素的位置（第一个元素/最后一个元素），而没有把序列分成较为均匀的两部分，在这种情况下，快速排序需要进行N轮，发挥不了分治法的优势，排序的
时间复杂度将会是O(n²)。
要解决上述问题，基准元素的选取我们可以不选取第一个元素，而是采用
随机选取基准元素。但是，即便是这样做，也有很小的几率选到数列的最大/最小元素作为基准元素，同样会影响分治的效果，所以快
速排序平均时间复杂度是nlog(n)，最坏时间复杂度是O(n²)。
三、快速排序的两种实现方法
看到这里，我们讨论了基准元素的选择，但是没有讨论快速排序具体的分治算法。现在已有的针对
快速排序的分治算法，比较典型的有两种，一种是
挖坑法，另一种是
指针交换法。下面我们来一一学习这两种算法。
3.1 挖坑法
什么是挖坑法呢？顾名思义，每一次我们先挖好一个“坑”，然后寻找符合条件的元素填入坑中，填坑的元素的位置又变成新的坑，重复这个过程（
挖坑—填坑—挖坑），直到寻找元素的
左右指针相交，相交的位置填入基准元素的值，一轮排序结束。用文字说明有些地方说的不够详细，而且有些抽象，下面用图来描述这个过程：
给定原始数列如下，要求从小到大排序：
首先，选择基准元素（这里选第一个元素），记住
基准元素的位置index，
值pivot，这个位置就是“坑”的位置，然后设置两个指针
left和right，分别指向序列的左右两端的端点：
接下来，移动right指针（
坑在最左边，则先移动right指针）。如果找到的元素
比privot大，则
right指针继续向左移动。直到找到
小于等于pivot的元素，
right指针就停止移动，并
把right指针所指的元素填入“坑”中，
left指针向右移一位。并且，
坑的指针指向right指针所指元素（挖一个新的“坑”）。
在这里，1<4，1填入坑，index指向right所指元素，同时left指针向右移一位：
此时，left左边绿色的区域代表着小于或等于基准元素的区域。
接下来，
切换到left指针进行比较。如果left指针所指的元素
小于等于pivot，那么
left指针继续右移，直到找到一个
比prvot大的元素，
left指针停止移动，并
把这个元素填入坑中，同时
right指针左移一位，
index指向left指针。
在这里，7>4，所以把7填入坑（index的位置），这时候元素7本来的位置成为了新的坑（index指向left），同时，right向左移动一位：
此时，right右边橙色的区域代表着大于基准元素的区域。
下面按照上述的思路继续排序：
8>4，元素位置不变，right左移：
2<4，用2来填坑，left右移，切换到left：
6>4，用6来填坑，right左移，切换到right：
3<4，用3来填坑，left右移，切换到left：
5>4，用5来填坑，right右移。这时候left和right重合在了同一位置：
这时候，把之前的pivot元素，也就是4放到index的位置。此时数列左边的元素都小于或等于4，数列右边的元素都大于4，这一轮交换终告结束。
一轮排序结束，重复上述过程，完成排序。
3.1.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
48
49
50
51
52
53
54
55
56
57
58
59
2 *
3 * @param arr 待排序的序列
4 * @param left 左指针的位置
5 * @param right 右指针的位置
6 */
7 public static void qucik_sort(int[] arr,int left,int right) {
8 //递归出口
9 if(left >= right) return;
10
11 //得到基准元素的位置
12 int pivot_index = partition_digHole(arr,left,right);
13
14 //对基准元素的左侧待排序序列进行排序
15 qucik_sort(arr,left,pivot_index - 1);
16
17 //对基准元素的右侧待排序序列进行排序
18 qucik_sort(arr,pivot_index + 1,right);
19 }
20
21 /**
22 * @param arr 待排序的序列
23 * @param left 左指针的位置
24 * @param right 右指针的位置
25 * @return 一轮交换之后基准元素所在位置
26 */
27 public static int partition_digHole(int[] arr,int left,int right) {
28 int pivot = arr[left];
29 int index = left;
30 while(right > left) {
31
32 //右指针左移，直到找到小于或等于基准元素的元素
33 while(right > left) {
34 if(arr[right] <= pivot) {
35 arr[index] = arr[right];//把找到的元素填坑
36 index = right;//坑指针指向右指针所指位置
37 left++;//左指针向右移动一位
38 break;
39 }
40 right--;//右指针左移
41 }
42
43 //左指针右移，直到找到大于基准元素的元素
44 while(right > left) {
45 if(arr[left] > pivot) {
46 arr[index] = arr[left];//把找到的元素填坑
47 index = left;//坑指针指向左指针所指位置
48 right--;//右指针向左移动一位
49 break;
50 }
51 left++;
52 }
53 }
54
55 //左右指针重合，跳出循环，重合的位置即为基础元素的位置。本轮排序结束
56 arr[index] = pivot;
57 return index;
58 }
59
3.2 指针交换法
指针交换法，相对于挖坑法来说，更容易理解，并且元素交换的次数更少：第一次循环，从right指针开始，如果
right指针所指向的元素大于pivot，那么
right指针左移，直到
right指针指向的元素小于或等于pivot，
right指针停止移动；切换到left指针，如果
left指针指向的元素小于或等于pivot，
left指针左移，直到
left指针指向的元素大于pivot，
left指针停止移动。然后把
left和right指针指向的元素互换，并进入第二次循环，
循环往复，直到
left指针和right指针重合，再把
重合的位置的元素与第一个元素互换（因为这里
选取的基准元素是序列的第一个元素，所以与第一个元素互换），本轮排序结束
给定原始数列如下，要求从小到大排序：
选定第一个元素为基准元素，取出基准元素的值保存在Pivot中，并且设置两个指针left和right，指向数列的最左和最右两个元素：
在当前数列中，1<4，所以right指针直接停止移动，换到left指针，进行下一步行动：
由于left指针一开始指向的是基准元素，判断肯定相等，所以left右移一位。由于7 > 4，left指针在元素7的位置停下。这时候，我们让left和right指向的元素进行交换：
接下来，我们进入第二次循环，重新切换到right向左移动。right先移动到8，8>4，继续左移。由于2<4，停止在2的位置：
切换到left，6>4，停止在6的位置：
元素6和2交换：
进入第三次循环，right移动到元素3停止，left移动到元素5停止：
元素5和3交换：
进入第四次循环，right移动到元素3停止，这时候请注意，left和right指针已经重合在了一起：
当left和right指针重合之时，我们让Pivot元素和left与right重合点的元素进行交换。此时数列左边的元素都小于或等于4，数列右边的元素都大于4，这一轮交换结束：
一轮排序之后，重复上述过程，完成排序。
3.2.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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
2 *
3 * @param arr 待排序的序列
4 * @param left 左指针的位置
5 * @param right 右指针的位置
6 */
7 public static void qucik_sort(int[] arr,int left,int right) {
8 //递归出口
9 if(left >= right) return;
10
11 //得到基准元素的位置
12 int pivot_index = partition_needleExc(arr,left,right);
13
14 //对基准元素的左侧待排序序列进行排序
15 qucik_sort(arr,left,pivot_index - 1);
16
17 //对基准元素的右侧待排序序列进行排序
18 qucik_sort(arr,pivot_index + 1,right);
19 }
20
21
22 /**
23 *
24 * @param arr 待排序的序列
25 * @param left 左指针的位置
26 * @param right 右指针的位置
27 * @return 一轮排序之后基准元素所在位置
28 */
29 public static int partition_needleExc(int[] arr,int left,int right) {
30 //基准元素所在位置
31 int index = left;
32
33 //基准元素的值
34 int pivot = arr[left];
35
36 //当左、右指针相交则一轮排序结束
37 while(right > left) {
38
39 //右指针左移，直到找到小于或等于pivot的元素，右指针停止移动
40 while(right > left && arr[right] > pivot) {
41 right--;
42 }
43
44 //左指针右移，直到找到大于pivot的元素，左指针停止移动
45 while(right > left && arr[left] <= pivot) {
46 left++;
47 }
48
49 //若左右指针还未相交，则交换此时左右指针所指元素
50 if(right > left) {
51 int temp = arr[left];
52 arr[left] = arr[right];
53 arr[right] = temp;
54 }
55 }
56
57 //左右指针相交，本轮排序结束，左右指针重合的位置即为基准元素所在的位置
58 int temp = arr[left];
59 arr[left] = arr[index];
60 arr[index] = temp;
61
62 return left;
63 }
64
四、注意点
** 1、为什么挖坑法是从右指针开始移动？**
答：因为本文实现的挖坑法，
基准元素选取的是左指针指向的元素，即最开始挖的坑是左指针指向的元素，所以需要从右指针开始寻找元素填入第一个坑中。
2、为什么指针交换法也是从右指针开始移动？
答：也是因为
选取的基准元素是左指针指向的元素（即第一个元素），指针交换法最后会把左右指针重合位置的元素和基准元素作交换，如果从左指针开始移动，那么会出现左右指针重合时所指向的元素比基准元素大的情况，与基准元素作交换以后，基准元素左边会出现比它大的元素，这显然是不可以的，所以我们要从右指针开始移动，避免出现上述情况。
五、快速排序的时间复杂度和稳定性分析
通过上面对面快速排序的分析，以及对快速排序进行代码实现，可以看出：
快速排序
最好情况下，时间复杂度为：
O(nlogn)；
快速排序
最坏情况下，时间复杂度为：
O(n²)；
快速排序的
平均时间复杂度为：
O(nlogn)；
快速排序的
稳定性：
不稳定；
