1. 荷兰国旗问题—三分类问题
题目描述：
给定一个数组和一个给定的值X，数组中的值根据X划分为两种或者三种情况：
（1）小于X的放在左边，等于X的放在中间，大于X的放在右边
（2）或者是小于等于X的放在左边，大于X的放在右边。
使用时间复杂度O(N)，空间复杂度为O(1)完成数组的调整， 划分的区域内部可以无序
拿破仑席卷欧洲大陆之后，代表自由，平等，博爱的竖色三色旗也风靡一时。荷兰国旗就是一面三色旗（只不过是横向的），自上而下为红白蓝三色。
该问题本身是关于三色球排序和分类的，由荷兰科学家Dijkstra提出。由于问题中的三色小球有序排列后正好分为三类，Dijkstra就想象成他母国的国旗，于是问题也就被命名为荷兰旗问题（Dutch National Flag Problem）
荷兰国旗问题：现在有若干个红、白、蓝三种颜色的球随机排列成一条直线。现在我们的任务是把这些球按照红、白、蓝排序。这个问题之所以叫荷兰国旗，是因为我们可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗。
下面是问题的正规描述： 现有n个红白蓝三种不同颜色的小球，乱序排列在一起，请通过两两交换任意两个球，使得从左至右，依次是一些红球、一些白球、一些蓝球。
给定数组arr[L,R]和目标数X，两种划分方式下的算法流程如下：
当划分为两种情况时：
初始小于等于区域边界为 L-1 大于区域边界为 R+1
1） 当前数 <= 目标数，把当前数和小于等于区的下一个数字做交换，然后小于等于区域向右扩，
当前数跳下一个。
2） 当前数 > 目标数，当前数直接跳下一个。当划分为三种情况时:
初始小于区域边界为 L-1 大于区域边界为 R+1
1） 当前数 < 目标数 当前数和小于区的下一个数字做交换，小于区域右扩一位，当前数字跳到下一个
2） 当前数 = 目标数 当前数当前数直接跳到下一个
3） 当前数 > 目标数 当前数和大于区的前一个交换，大于区域向左扩一位，当前数字停在原地不变
当前数和右边界撞上的时候停止。写法升级
给定一个数组arr[L,R]，直接arr[R]作为这个目标值，也就是相当于在前两者的基础上，实现arr[L,R-1]和目标值arr[R]进行比较排序，排序结束后将arr[R]和大于区域的第一个数做交换，即可实现，arr[L,R]上以arr[R]为划分值来归类排序。
举例：具体流程如下：
- 荷兰国旗问题代码实现：
// arr[L...R] 荷兰国旗问题的划分，以arr[R]做划分值// 实现数组划分为三个区域<arr[R] ==arr[R] >arr[R]// 返回值为等于区域的坐标public static int[] netherlandsFlag(int[] arr, int L, int R) {if (L > R) { // L...R L>Rreturn new int[] { -1, -1 };}if (L == R) {return new int[] { L, R };}int less = L - 1; // < 小于区 大于区左边界为L-1int more = R; // > 大于区 以arr[R]作为划分值X，划分区域在L~R-1上，大于区左边界为Rint index = L;while (index < more) { // 当前位置，不能和 大于区 的左边界撞上if (arr[index] == arr[R]) { // 当前数和划分数相等，当前数字直接跳到下一个index++;} else if (arr[index] < arr[R]) { // 当前数小于目标数// swap(arr, less + 1, index); // 小于区域的下一个数和当前数交换// less++; // 小于区域向右扩// index++; // 当前数跳到下一个swap(arr, index++, ++less);} else { // > // 当前数大于目标数// 当前数和大于区的前一个交换，大于区域向左扩，当前数字停在原地// swap(arr, more - 1, index);// more--;swap(arr, index, --more); //}}swap(arr, more, R); // <[R] =[R] >[R] // 最后将划分值和大于区域的第一个数做交换，让arr[R]归为return new int[] { less + 1, more };}
2. 随机快速排序
快排 1.0 O(N2) 1 2 3 4 5 6 7 这种情况时间复杂度为O(N2)
快排 2.0 O(N2)
快排 3.0
3. 快排递归和非递归代码实现
public class Code03_QuickSortRecursiveAndUnrecursive {// 荷兰国旗问题,arr[L...R] 荷兰国旗问题的划分，以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 };}int less = L - 1;int more = R;int index = L;while (index < more) {if (arr[index] == arr[R]) {index++;} else if (arr[index] < arr[R]) {swap(arr, index++, ++less);} else {swap(arr, index, --more);}}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;}// 快排递归版本public static void quickSort1(int[] arr) {if (arr == null || arr.length < 2) {return;}process(arr, 0, arr.length - 1);}public static void process(int[] arr, int L, int R) {if (L >= R) {return;}// 每次随机生成一个基准数pivotswap(arr, L + (int) (Math.random() * (R - L + 1)), R);int[] equalArea = netherlandsFlag(arr, L, R);process(arr, L, equalArea[0] - 1);process(arr, equalArea[1] + 1, R);}// 快排非递归版本需要的辅助类// 要处理的是什么范围上的排序，表示处理 l r 上排序public static class Op {public int l;public int r;public Op(int left, int right) {l = left;r = right;}}// 快排3.0 非递归版本public static void quickSort2(int[] arr) {if (arr == null || arr.length < 2) {return;}int N = arr.length;swap(arr, (int) (Math.random() * N), N - 1); // 随机选择一个数字与最右侧的数作交换。int[] equalArea = netherlandsFlag(arr, 0, N - 1); // 区域划分 小于 等于 大于int el = equalArea[0];int er = equalArea[1];Stack<Op> stack = new Stack<>(); // 操作栈stack.push(new Op(0, el - 1)); // 左侧stack.push(new Op(er + 1, N - 1));// 右侧while (!stack.isEmpty()) {Op op = stack.pop(); // op.l ... op.rif (op.l < op.r) {swap(arr, op.l + (int) (Math.random() * (op.r - op.l + 1)), op.r);equalArea = netherlandsFlag(arr, op.l, op.r);el = equalArea[0];er = equalArea[1];stack.push(new Op(op.l, el - 1));stack.push(new Op(er + 1, op.r));}}}// 生成随机数组（用于测试）public static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// 拷贝数组（用于测试）public static int[] copyArray(int[] arr) {if (arr == null) {return null;}int[] res = new int[arr.length];for (int i = 0; i < arr.length; i++) {res[i] = arr[i];}return res;}// 对比两个数组（用于测试）public static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {return false;}if (arr1 == null && arr2 == null) {return true;}if (arr1.length != arr2.length) {return false;}for (int i = 0; i < arr1.length; i++) {if (arr1[i] != arr2[i]) {return false;}}return true;}// 打印数组（用于测试）public static void printArray(int[] arr) {if (arr == null) {return;}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}// 跑大样本随机测试（对数器）public static void main(String[] args) {int testTime = 500000;int maxSize = 100;int maxValue = 100;boolean succeed = true;System.out.println("test begin");for (int i = 0; i < testTime; i++) {int[] arr1 = generateRandomArray(maxSize, maxValue);int[] arr2 = copyArray(arr1);quickSort1(arr1);quickSort2(arr2);if (!isEqual(arr1, arr2)) {succeed = false;break;}}System.out.println("test end");System.out.println("测试" + testTime + "组是否全部通过：" + (succeed ? "是" : "否"));}}
package class05;
public class Code02_PartitionAndQuickSort {
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
// arr[L..R]上，以arr[R]位置的数做划分值X,
// <= X 放左， > X放右，而且要求在<=X的区域里最后一个数是X
// <= X X
public static int partition(int[] arr, int L, int R) {
if (L > R) {
return -1;
}
if (L == R) {
return L;
}
int lessEqual = L - 1;
int index = L;
while (index < R) {
if (arr[index] <= arr[R]) {
swap(arr, index, ++lessEqual);
}
index++;
}
swap(arr, ++lessEqual, R);
return lessEqual;
}
// arr[L...R] 玩荷兰国旗问题的划分，以arr[R]做划分值
// <arr[R] ==arr[R] > arr[R]
public static int[] netherlandsFlag(int[] arr, int L, int R) {
if (L > R) { // L...R L>R
return new int[] { -1, -1 };
}
if (L == R) {
return new int[] { L, R };
}
int less = L - 1; // < 区 右边界
int more = R; // > 区 左边界
int index = L;
while (index < more) { // 当前位置，不能和 >区的左边界撞上
if (arr[index] == arr[R]) {
index++;
} else if (arr[index] < arr[R]) {
// swap(arr, less + 1, index);
// less++;
// index++;
swap(arr, index++, ++less);
} else { // >
swap(arr, index, --more);
}
}
swap(arr, more, R); // <[R] =[R] >[R]
return new int[] { less + 1, more };
}
public static void quickSort1(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process1(arr, 0, arr.length - 1);
}
public static void process1(int[] arr, int L, int R) {
if (L >= R) {
return;
}
// L..R partition arr[R] [ <=arr[R] arr[R] >arr[R] ]
int M = partition(arr, L, R);
process1(arr, L, M - 1);
process1(arr, M + 1, R);
}
public static void quickSort2(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process2(arr, 0, arr.length - 1);
}
// arr[L...R] 排有序，快排2.0方式
public static void process2(int[] arr, int L, int R) {
if (L >= R) {
return;
}
// [ equalArea[0] , equalArea[0]]
int[] equalArea = netherlandsFlag(arr, L, R);
process2(arr, L, equalArea[0] - 1);
process2(arr, equalArea[1] + 1, R);
}
public static void quickSort3(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process3(arr, 0, arr.length - 1);
}
public static void process3(int[] arr, int L, int R) {
if (L >= R) {
return;
}
swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
int[] equalArea = netherlandsFlag(arr, L, R);
process3(arr, L, equalArea[0] - 1);
process3(arr, equalArea[1] + 1, R);
}
}
// 切分元素，分成<=指标值(arr[]) 的和 大于指标值(arr[])的两组
public static int partition(int[] arr, int L, int R) {
if (L > R) {
return -1;
}
if (L == R) {
return L;
}
int lessEqual = L - 1;
int index = L;
while (index < R) {
if (arr[index] <= arr[R]) { // 小于等于时，当前数和小于等于区后一位交换， lessEqual++, index++
swap(arr, index, ++lessEqual);
}
index++;
}
swap(arr, ++lessEqual, R); // 最后一个数和
return lessEqual;
}
public static void quickSort1(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process1(arr, 0, arr.length - 1);
}
// 快排1.0版本
public static void process1(int[] arr, int L, int R) {
if (L >= R) {
return;
}
// L..R partition arr[R] [ <=arr[R] arr[R] >arr[R] ]
int M = partition(arr, L, R);
process1(arr, L, M - 1);
process1(arr, M + 1, R);
}
public static void quickSort2(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process2(arr, 0, arr.length - 1);
}
// arr[L...R] 排有序，快排2.0方式
public static void process2(int[] arr, int L, int R) {
if (L >= R) {
return;
}
// [ equalArea[0] , equalArea[1]] 返回等于区域的范围
int[] equalArea = netherlandsFlag(arr, L, R);
process2(arr, L, equalArea[0] - 1);
process2(arr, equalArea[1] + 1, R);
}
public static void quickSort3(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process3(arr, 0, arr.length - 1);
}
// 随机快排，这个才是学术界所说的快速排序。
public static void process3(int[] arr, int L, int R) {
if (L >= R) {
return;
}
// 在之前的版本中，arr中位于R位置的数作为划分值，标志物的选择都是将每次划分数组的最右侧作为划分值来做比较，小于该值的
// 放在左边，大于该值的放在右边。而随机快速排序也就是三版本，采用的是随机选择一个数字
// h换到最右边去，选择arr中L-R上随机一个数字与R位置的数做交换，之后在进行2版本的操作。
//
swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
int[] equalArea = netherlandsFlag(arr, L, R);
process3(arr, L, equalArea[0] - 1);
process3(arr, equalArea[1] + 1, R);
}
Master公式计算递归算法的时间复杂度：
快排的时间复杂度: O(N*logN)
随机快排，比较值或者划分值的选择，在最好情况下是每次选择之后划分左右的数字个数大致是相等的。
因此当划分值选择的比较好的情况下，快排的时间复杂度会向 O(N*logN)收敛，当划分值选择的不好的情况下，时间复杂度会向O(N2) 收敛。
T(N) = O(N2) + 2T(N/2)_ => O(NlogN)
概率事件数学证明：时间复杂度为 O(N*logN_)
快排的额外空间复杂度：O(logN)
最差的情况 O(N)，最好情况 O(logN)
递归占用的额外空间，中间划分点信息需要记录下来，这个划分值需要记录下来，如果不记录下来，当做完左侧的递归之后，回去找不到划分值，此时就无法进行右侧的递归了，找不到右侧递归范围了；
如果不使用递归的形式，需要自己维护一个栈来记录这个每次划分值的信息
最差情况： 1 2 3 4 5 6 7 ，每一个点都需要记录，O(N)
最好情况： 每次都是中点为划分值，通过重复释放利用，只需要logN的额外空间，通过变量的不断释放、复用、释放、复用达到最好情况.
概率事件最终额外空间复杂度收敛到 O(logN)
若有收获，就点个赞吧
0 人点赞
