​
​

活动地址：CSDN21天学习挑战赛

荷兰国旗问题

给定一个数组arr，和一个整数num。请把小于num的数放在数组的左边，等于num的数放在中间，大于num的数放在数组的右边。
要求额外空间复杂度O(1)，时间复杂度O(N)
把数组排成像荷兰国旗一样,分为3块,左边为小于区,中间为等于区,右边为大于区
那么我们要怎么分呢

荷兰国旗解题思路

首先我们先定义小于区less和大于区more
我们分出三种情况
1.当前数等于目标数,下标直接加1,不做交换
2. 当前数小于目标数,当前数与小于区的下一个元素交换,小于区扩大,下标加1
3. 当前数大于目标数,当前数与大于区上一个元素交换,大于区扩大,下标不变

当index来到0位置,当前数为1,为第二种情况,小于区扩大,index++

现在index来到1位置,为第三种情况,index的数与大于区前一个数交换,大于区扩大

依旧为第三种情况,index的数与大于区前一个数交换,大于区扩大

继续交换

后面几步都是第三种情况,我们先跳过,来看第一种情况

现在index的数与目标数相等,小于和大于区都不变,index直接加一


大于区扩大,index>=more.退出

荷兰国旗代码

	//在快排中,我们假设最后一个数为目标数
	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 };
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

荷兰国旗到快排

我们已经了解了荷兰国旗问题,那么快排的过程就是
1）在这个范围上，随机选一个数记为num，
2）用num对该范围做partition(荷兰国旗问题)，< num的数在左部分，== num的数中间，>num的数在右部分。假设== num的数所在范围是[a,b]
3）对arr[L…a-1]进行快速排序(递归)
4）对arr[b+1…R]进行快速排序(递归)

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;
		}
		//在L和R中随机把一个数交换到r位置
		swap(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);
	}


	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 };
	}
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

时间复杂度分析

1）通过分析知道，划分值越靠近中间，性能越好；越靠近两边，性能越差
2）随机选一个数进行划分的目的就是让好情况和差情况都变成概率事件
3）把每一种情况都列出来，会有每种情况下的时间复杂度，但概率都是1/N
4）那么所有情况都考虑，时间复杂度就是这种概率模型下的长期期望！
因此时间复杂度为O(n*logn)

稳定性分析

稳定性是指同样大小的样本再排序之后不会改变相对次序
因为快排在做partition过程中,破坏了数组元素的相对次序,因此快排无法做到稳定
快速排序稳定性可以进行改进，“01 stable sort”，但是会对样本数据要求更多