荷兰国旗问题

问题描述
拿破仑席卷欧洲大陆之后，代表自由，平等，博爱的竖色三色旗也风靡一时。荷兰国旗就是一面三色旗（只不过是横向的），自上而下为红白蓝三色。该问题本身是关于三色球排序和分类的，由荷兰科学家 Dijkstra 提出。由于问题中的三色小球有序排列后正好分为三类，Dijkstra 就想象成他母国的国旗，于是问题也就被命名为荷兰旗问题（Dutch National Flag Problem）。下面是问题的正规描述： 现有 n 个红白蓝三种不同颜色的小球，乱序排列在一起，请通过两两交换任意两个球，使得从左至右，依次是一些红球、一些白球、一些蓝球。在算法中，更多这样描述：如何通过两两交换，将一个数组中小于 N 的数放在靠左边，等于 N 的数放在靠中间，大于 N 的数放在靠右边 ；比如，数组 arr[1, 14, 5, 16, 8, 7], N=8, 则两两交换后得到[1, 7, 5, 8, 16, 14]。注意，左右两边内部不一定有序 。

问题分析
设计一个大(右)小(左)区间，通过不断扩展区间达到 分区(partition) 的效果。过程图示如下：

有以下几点需要注意：

  1. 左区间的初始位置为 L=-1，右区间的初始位置为 R=size；
  2. 当指针(下标为T)指向的数

    • 小于 N 时：交换 arr[T] 和 arr[L+1] ，T++ ，L++；

    • 等于 N 时，T++；

    • 大于 N 时，交换 arr[T] 与 arr[R-1]，R–，不可 T++ ！！！！！！！！！！！！

  3. T >= R 时，过程结束。注意，结束条件不能设置为 T==R，因为 R–，T++，可能有 T-R=1
  4. 区间内部不保证有序

代码实现 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void netherLandFlag(int* arr, int size, int N)
{
	int L = -1;
	int R = size;
	int T = 0;
	while (T < R)
	{
		if (arr[T] < N)
			swap(arr[T++], arr[++L]);
		else if (arr[T] = N)
			T++;
		else
			swap(arr[T], arr[--R]);
	}
}

快速排序1.0

快速排序的核心就是递归调用荷兰国旗方法 。由于一旦完成 partition，中间区间(等于N的数)就不会再移动，所以就能通过不断在左右区间内部继续划分区间，直到无法划分为止，最终达到排序的效果 。在快速排序中，N 并不是上述那样人为指定的，而是固定为当前区间中最右边的那个数 。如下图：

注意：

  1. 不同于之前 R=size，这里 R = size-1；
  2. 最后需要指定交换 arr[R] 与 arr[size-1]；

代码实现 

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
struct loc
{
	int left;
	int right;
};

loc netherLandsFlag(int* arr, int lower, int upper)
{
	loc bound;
	if (lower == upper)
	{
		bound.left = bound.right = lower;
		return bound;
	}
	int L = lower - 1; 
	int R = upper;
	int index = lower;
	while (index < R)
	{
		if (arr[index] < arr[upper])
			swap(arr[index++], arr[++L]);
		else if (arr[index] == arr[upper])
			index++;
		else
			swap(arr[index], arr[--R]);
	}
	swap(arr[R], arr[upper]);
	bound.left = L;
	bound.right = R + 1;
	return bound;
}

void process(int* arr, int lower, int upper)
{
	if (lower >= upper)
		return;
	loc bound = netherLandsFlag(arr, lower, upper);
	process(arr, lower, bound.left);
	process(arr, bound.right, upper);
}
  • 注意第 21 行的 swap，容易忽略；
  • 基线条件是 lower>=upper，而不是 lower==upper；
  • 第 29 行，右边界下标为 R+1 而非 R ；

快速排序2.0——随机快排

阅读上文后，读者也许能敏锐地发现，区间的划分情况和 N 息息相关。我们希望，N 总是可以打到数组的中间(数值, 而非位置)，这样每次划分就可以达到类似于二分的效果；而一旦数组偏有序，那么划分次数就会大大增加 ，如下：

第 K 层比较次数为 N-K 次，笼统记为 N 次( 只要与 N 线性相关，都记为 N )；一共 N-1 层，笼统记为 N 层；所以时间复杂度为 O(N2)O(N^2) 。

如果每次打到中间，就可以产生二分效果，减少划分次数，如下：
上图中比较5次更正为6次

第 K 层比较次数为 N-K 次，笼统记为 N 次；一共有 log2Nlog_2N 层( log27=2log_27=2 )，笼统记为 logNlogN ，故时间复杂度为 NlogNNlogN 。

那么如何使 N 刚好打到数组的数值正中间呢？遗憾的是，无法做到，只能随机取值。但好消息是，将 N 随机取值(其值必须为数组中的数)后，该算法的长期期望也可以达到 NlogNNlogN 。在最坏状况下则需要次 O(N2)O(N^2) 比较，但这种状况并不常见。

代码实现 

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<cstdlib>//rand()
#include<ctime>//time()
#include<cstring>//memcpy()
#include<vector>

struct loc
{
	int left;
	int right;
};

int* generateRandomArr(int max, int len) {//生成随机数组
	int* arr = new int[len];
	for (int i = 0; i < len; i++)
		arr[i] = rand() % max;
	return arr;
}

void swap(int& a, int& b)
{
	int tmp = a;
	a = b;
	b = tmp;
}

loc netherLandsFlag(int* arr, int lower, int upper)
{
	loc bound;
	if (lower == upper)
	{
		bound.left = bound.right = lower;
		return bound;
	}
	int L = lower - 1; 
	int R = upper;
	int index = lower;
	while (index < R)
	{
		if (arr[index] < arr[upper])
			swap(arr[index++], arr[++L]);
		else if (arr[index] == arr[upper])
			index++;
		else
			swap(arr[index], arr[--R]);
	}
	swap(arr[R], arr[upper]);
	bound.left = L;
	bound.right = R + 1;
	return bound;
}

void process(int* arr, int lower, int upper)
{
	if (lower >= upper)
		return;
	swap(arr[upper], arr[rand() % (upper - lower + 1) + lower]);
	loc bound = netherLandsFlag(arr, lower, upper);
	process(arr, lower, bound.left);
	process(arr, bound.right, upper);
}

void quickSort(int* arr, int size)
{
	if (arr == nullptr || size == 1)
		return;
	process(arr, 0, size - 1);
}
  • 第 57 行，随机交换数组最后和其他某位置的数。

效率比较

测试次数time=10000 ，最大值max=1000000000 ，最大长度size=1000000 ，快速排序 1.0 反而快于随机快排 0.6203 ms ：

image-20220920231457291

这稍显离谱。。。。。原因咱不知晓，后续探究。

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<iostream>
#include<cstdlib>//rand()
#include<ctime>//time()
#include<cstring>//memcpy()
#include<vector>

struct loc
{
	int left;
	int right;
};

int* generateRandomArr(int max, int len) {//生成随机数组
	int* arr = new int[len];
	for (int i = 0; i < len; i++)
		arr[i] = rand() % max;
	return arr;
}

void swap(int& a, int& b)
{
	int tmp = a;
	a = b;
	b = tmp;
}

loc netherLandsFlag(int* arr, int lower, int upper)
{
	loc bound;
	if (lower == upper)
	{
		bound.left = bound.right = lower;
		return bound;
	}
	int L = lower - 1; 
	int R = upper;
	int index = lower;
	while (index < R)
	{
		if (arr[index] < arr[upper])
			swap(arr[index++], arr[++L]);
		else if (arr[index] == arr[upper])
			index++;
		else
			swap(arr[index], arr[--R]);
	}
	swap(arr[R], arr[upper]);
	bound.left = L;
	bound.right = R + 1;
	return bound;
}

void process_1(int* arr, int lower, int upper)
{
	if (lower >= upper)
		return;
	loc bound = netherLandsFlag(arr, lower, upper);
	process_1(arr, lower, bound.left);
	process_1(arr, bound.right, upper);
}

void quickSort_1(int* arr, int size)
{
	if (arr == nullptr || size == 1)
		return;
	process_1(arr, 0, size - 1);
}


void process_2(int* arr, int lower, int upper)
{
	if (lower >= upper)
		return;
	swap(arr[upper], arr[rand() % (upper - lower + 1) + lower]);
	loc bound = netherLandsFlag(arr, lower, upper);
	process_2(arr, lower, bound.left);
	process_2(arr, bound.right, upper);
}

void quickSort_2(int* arr, int size)
{
	if (arr == nullptr || size == 1)
		return;
	process_2(arr, 0, size - 1);
}

int* cpyArr(int* src, int len) {
	int* des = new int[len];
	memcpy(des, src, len * sizeof(int));
	return des;
}

bool isEqual(int* arr_1, int* arr_2, int len) {
	for (int i = 0; i < len; i++) {
		if (arr_1[i] != arr_2[i])
			return false;
	}
	return true;
}

int main()
{
	clock_t start_1, end_1,start_2,end_2;
	
	srand((unsigned)time(NULL));
	int max = 1000000000;
	int maxSize = 1000000;
	int times = 10000;
	int arg=0;
	for (int i = 0; i < times; i++)
	{
		int size = rand() % maxSize + 1;
		int* arr_1 = generateRandomArr(max, size);
		int* arr_2 = cpyArr(arr_1, size);
		start_1 = clock();
		quickSort_1(arr_1, size);
		end_1 = clock();

		start_2 = clock();
		quickSort_2(arr_2, size);
		end_2 = clock();
		if (isEqual(arr_1, arr_2, size) == false)
		{
			std::cout << "排序出错!" << std::endl;
			exit(1);
		}
		std::cout << "一般快速排序：" << end_1 - start_1 << " ms" << std::endl;
		std::cout << "随机快速排序：" << end_2 - start_2 << " ms" << std::endl;
		std::cout << "后者快于前者：" << end_1 - start_1 - (end_2 - start_2) << " ms" << std::endl;
		arg += end_1 - start_1 - (end_2 - start_2);
	}
	std::cout << "==========================================" << std::endl << "平均快于" << (double)arg/times << " ms";	
}