一、实现思路

1.寻找一个位于数列中部的数字，记为pivot。

2.分别在目标数段的左端和右端开始遍历，在左方，寻找值大于或等于pivot的数字，在右方，寻找值小于或等于pivot的数字，并且依此交换。

3.完成一轮交换后，在pivot的左方应为无序但都小于pivot的数字段，右方同理。

4.使用递归，分别在pivot的左方和右方再次调用快速查找的方法。

二、代码实现

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
public void quickSort(int[] arr, int left, int right) {
       int l = left; //左方开始的点
       int r = right; //右方开始的点
       int pivot =arr[(left + right) / 2]; //中间值
       int temp; //临时变量，用于数列不同位置交换数值
       while (l < r) { //当左点小于右点时，意味着数列未遍历完毕，继续执行代码。
           while (arr[l] < pivot) {
               l++;  //左方数值小于pivot,继续遍历。大于pivot,跳出循环，arr[l]即为需要交换的数值
           }
           while (arr[r] > pivot) {
               r--;  //同理
           }
           if (l >= r) break; //满足此条件需要及时跳出循环，以免执行后续代码可能导致越界访问数组报错。
           temp = arr[l];
           arr[l] = arr[r];
           arr[r] = temp; //交换符合需求的数值
           if (arr[r] == pivot) l++;
           if (arr[l] == pivot) r--; //防止出现死循环(下面详谈)
	}
       if (r == l) {
           r--;
           l++;
       } //防止出现死递归导致栈溢出
       if (left < r) {
           quickSort(arr, left, r);
       }
       if (l < right) {
           quickSort(arr, l, right);
       } //不满足条件则退出递归，满足条件则再次调用方法。
   }

三、代码分析

1.防止出现死循环或排序不准的代码块

1
2
3
4
{
 if (arr[r] == pivot) l++;
 if (arr[l] == pivot) r--;
}

如果没有这段代码，程序可能会出现死循环。假如遇到[……, 11, ……, 11, ……]此形式的数组，且pivot值恰为11，左右数值在遍历到左右端的11时，会触发条件进行交换。交换后仍满足交换条件，便会再次进行交换，进入死循环。
（学习误区记录：初学时错误认为只有当两边都等于pivot值时才会发生死循环，而这段代码一读到与pivot数值相同的数字就会执行，认为没有必要，将代码改为：

1
2
3
4
if (arr[r] == arr[l] && arr[r] == pivot) {
	l++;
	r--;
	}

这样虽然能避免死循环，但是可能会出现排序错乱的情况。比如数组[……, 11, 8, 7, 11, ……], pivot为11，当左右两端恰好都读到11时，执行上述代码，虽然能避免死循环，但是左右端分别指向8和7，并且后续不会进行交换，显然错误。

2.防止死递归导致栈溢出的代码块

1
2
3
4
if (r == l) {
	r--;
    l++;
}

如果没有此代码块，在递归过程中不会有影响。但是会影响递归结束判断，造成死递归。比如在递归到数组[1， 2]部分， left = 0, right = 1, pivot = 1, 当左右点在1处相遇时，结束遍历，也应当结束递归，如果缺少上述代码块，l < right 条件仍然成立， 又会执行quickSort(arr, l, right);并且下一次执行的数组也是left = 0, right = 1, pivot = 1,所以会死递归导致栈溢出。

3.防止出现越界访问数组报错的代码块

1
if (l >= r) break;

如果没有此代码块，可能会出现越界访问数组报错。比如[……, 11] ，且pivot恰好为11，右点指向此11时， 若恰好左点也指向数组末尾的同一11，此时应当执行上述代码块跳出循环。若没有上诉代码块，满足arr[r] == pivot的条件，则会执行代码l++, 此时l的值就会超出数组范围，当再次进入循环执行判断语句arr[l] < pivot时，便会越界访问数组，进行报错。

此次学习的视频：
【尚硅谷】数据结构与算法（Java数据结构与算法） （66 ~ 68）

​