一.荷兰国旗问题
给定一个数组arr，和一个数num，请把小于num的数放在数组的
左边，等于num的数放在数组的中间，大于num的数放在数组的
右边。荷兰最早采用横条三色旗
-
思路就是：
1.开始时先设一个变量cur,用来指向当前分量。
less与more分别用来表示“小于区”、“大于区”的“范围 位置”。less在-1处，more在arr.length处
起始
2.开始遍历。若cur指向的数小于num，将此数与 “小于区” 的下一个数位置交换（4移动到0位置，即位置没变）。 接着cur++；less++“小于区”扩大。
分量比num小的情况
3.cur指向的值为5，与num相等。这时直接cur++跳往下一个分量，相当于5在 “等于区”。分量等于num的情况
4.此时，cur指向的数为9，比num大。这时将cur指向的数9与 “大于区”的前一个数交换位置。 more--，大于区扩大；
因为从右侧而来的数的值不好确定，所以curr不变，需要再次判断移过来的数值大小并进行相应操作。分量大于num的情况
5.接下来判断出cur所指的值是6依然大于num，与“大于区”前一个数 1 交换位置，more--“大于区”扩大。
cur不变继续判断，1被交换至此，小于num。则 1 与“小于区”后一个数5交换位置，less++，cur++。
操作后cur不变再次判断的情况
6.最后呢，在cur==more时，递归结束。（没有“大于区”时也是如此）结束
二.经典快速排序
在写改进版快排前，先复习一下经典快速排序快速排序需要划分成这两个区域
1.这里将数组的最后一个位置的数作为 “划分值”并移出。
2.“右拆左补”：left++从左向右扫描，遇到比“划分值”大的数，就把它移到空缺处；
“左拆右补”：接着right- -向左扫描，碰到比小于等于“划分值”的数就移到左边的空缺处。
三.改进快速排序
在上图在第一次排序后，“分而治之”之前，左侧被划分区域还有一个“6”呢。若是将小于还有大于“6”的区域的数拿出去继续递归，等于“6”的部分不要动，是不是会好一些？
所以经典快速排序有一个缺点，就是每次排序只能确定好一个数，效率会比较低；
如何改造呢：根据前面提到的荷兰国旗问题, 在快速排序中增加一个“=X”区域
-
步骤简述：
1.变量cur表示当前指向的数组元素。变量less与more分别代表大于区小于区的“位置 范围”
将数组的最后一个元素值设为“划分值”。并暂归入“大于区”中。
q2.png
2.元素4被纳为小于区；经过两个相同的划分值元素后，cur所指的值大于“6”，所以要与“大于区”前一个分量交换。
q3.png
3.再次当前判断cur所指元素的值并继续。
4.终止条件是 cur==more。返回“等于区”的范围是：less+1 至 more。
接着两侧区域的数组重复相同操作，最终得到有序数组。
- 代码实现
/**
* 改进版快速排序代码
*/
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int L, int R) {
if (L < R) {
int[] p = partition(arr, L, R);
quickSort(arr, L, p[0] - 1); //p[0]不属于"小于区"
quickSort(arr, p[1] + 1, R); //p[1]不属于"大于区"
}
}
//返回一个存有"等于区域"的下标的数组
public static int[] partition(int[] arr, int L, int R) {
int less = L - 1;
int more = R; //将最后一个数作为划分值
int cur = L;
while (cur < more) {
if (arr[cur] < arr[R]) {
swap(arr, ++less, cur++);
//++less表示在交换元素时指向“小于区”的下一个数，
//cur++表示交换完成后指向下一个数组元素
} else if (arr[cur] > arr[R]) {
swap(arr, --more, cur);
//cur不动，将继续判断其所指向的值
} else { //当前值等于判定值
cur++;
}
}
swap(arr, more, R); //将判定值放入“等于区域”中
return new int[] { less + 1, more };
}
//实现数组分量的交换
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
