共计 3255 个字符，预计需要花费 9 分钟才能阅读完成。
大家好，我是周一。
最近几篇算法，咱们都是聊的归并排序，归并排序也说的差不多了，明天聊聊疾速排序。
一、荷兰国旗问题
1、啥是荷兰国旗问题
荷兰国旗是由红白蓝 3 种颜色的条纹拼接而成，如下图所示：
假如这样的条纹有多条，且各种色彩的数量不一，并且随机组成了一个新的图形，新的图形可能如下图所示，但不仅仅只有这一种状况：
需要是：把这些条纹依照色彩排好，红色的在上半局部，红色的在两头局部，蓝色的在下半局部，咱们把这类问题称作荷兰国旗问题。
2、荷兰国旗问题的形象
咱们 把荷兰国旗问题形象成数组 的模式是上面这样的：
给定一个整数数组和一个值 M（存在于原数组中），要求把数组中小于 M 的元素放到数组的右边，等于 M 的元素放到数组的两头，大于 M 的元素放到数组的左边，最终返回一个整数数组，只有两个值，0 地位是等于 M 的数组局部的左下标值、1 地位是等于 M 的数组局部的右下标值。
进一步 形象为更加通用 的模式是上面这样的：
给定数组 arr，将 [l, r] 范畴内的数（当然默认是 [0 – arr.length – 1]），小于 arr[r]（这里间接取数组最左边的值进行比拟）放到数组右边，等于 arr[r]放到数组两头，大于 arr[r]放到数组左边。最初返回等于 arr[r]的左, 右下标值。
3、解决的思路
定义一个小于区，一个大于区；遍历数组，挨个和 arr[r]比拟，
（1）小于 arr[r]，与小于区的后一个地位替换，以后地位后移；
（2）等于 arr[r]，以后地位间接后移；
（3）大于 arr[r]，与大于区的前一个地位替换，以后地位不动（替换到此地位的数还没比拟过，所以不动）。
遍历完后，arr[r]和大于区的最左侧地位替换。
最初返回，此时小于区的后一个地位，大于区的地位，即是最初的等于 arr[r]的左, 右下标值。
4、具体的参考代码
/**
* 荷兰国旗问题
* <p>
* 把数组 arr 中，[l, r]范畴内的数，小于 arr[r]放到数组最右边，等于 arr[r]放到数组两头，大于 arr[r]放到数组最左边
*
* @return 返回等于 arr[r]的左, 右下标值
*/
public static int[] netherlandsFlag(int[] arr, int l, int r) {if (l > r) {return new int[]{-1, -1};
}
if (l == r) {return new int[]{l, r};
}
// 小于 arr[r]的右边界，从 L 的右边一位开始
int less = l - 1;
// 大于 arr[r]的左边界，从 r 开始，即以后右边界里曾经有 arr[r]
int more = r;
// 以后正在比拟的下标
int index = l;
// 不能与 大于 arr[r]的左边界 撞上
while (index < more) {if (arr[index] < arr[r]) {// 小于时，将以后地位的数和小于 arr[r]的右边界的下一个地位替换
// 以后地位后移一位
swap(arr, index++, ++less);
} else if (arr[index] == arr[r]) {
// 等于时，以后地位后移一位即可
index++;
} else {// 大于时，以后地位的数和大于 arr[r]的左边界的前一个地位替换
// 以后地位不动
swap(arr, index, --more);
}
}
// 将 arr[r]地位的数和大于 arr[r]的左边界的数替换
// 此时整个数组就依照 小于、等于、大于 arr[r] 分成了左中右三块
swap(arr, more, r);
// 最初整个数组中，等于 arr[r]的左右边界别离是 less + 1, more
return new int[]{less + 1, more};
}
二、疾速排序
1、啥是快排（排序流程）
首先设定一个分界值，通过该分界值将数组分成左中右三局部。
（1）将小于分界值的数据集中到数组的右边，等于分界值的数据集中到数组的两头，大于分界值的数据集中到数组左边。
（2）而后，右边和左边的数据能够独立排序。对于左侧的数据，又能够取一个分界值，将该局部数据分成左中右三局部，同样在右边放较小值，两头放等于值，左边放较大值。左边数据也做同样的解决。
（3）反复上述过程，能够看出，这是一个递归过程。通过递归将左侧局部排好序后，再递归排好右侧局部的程序。当左、右两个局部各数据排序实现后，整个数组的排序也就实现了。
当看完了快排的流程，是不是发现快排的外围办法就是荷兰国旗问题，所以晓得为啥本文一开始就介绍荷兰国旗问题了吧。
2、形象后的快排流程
（1）随机将数组中的某个数放到比拟地位上（即最右侧地位）
（2）调用荷兰国旗办法，（此时等于区的数即在最初排好序的地位上），拿到等于区的左右下标
（3）小于区和大于区再各自递归调用（1）（2）步即可将小于区和大于区排好序。
3、具体的参考代码
/**
* 随机快排
*/
public static void quickSortRandom(int[] arr) {if (arr == null || arr.length < 2) {return;}
processRandom(arr, 0, arr.length - 1);
}
private static void processRandom(int[] arr, int l, int r) {if (l >= r) {return;}
// 随机将数组中的某个数放到比拟地位上（即数组最左边地位）// 这一步是保障快排工夫复杂度是 O(N*logN)的要害，不然，快排的工夫复杂度是 O(N^2)
swap(arr, l + (int) ((r - l + 1) * Math.random()), r);
// 将数组划分为 小于、等于、大于 arr[r] 的左中右三块
int[] equalArea = netherlandsFlag(arr, l, r);
// 此时等于区域的值曾经处于最初排序后果的地位了
// 递归将左半局部的排好序
processRandom(arr, l, equalArea[0] - 1);
// 递归将右半局部的排好序
processRandom(arr, equalArea[1] + 1, r);
}
public static void swap(int[] arr, int i, int j) {int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
