bachzart's Blog
0%

ZJU_DS_10-排序（下）

Posted on Edited on In ,

本周继续介绍排序算法。

快速排序

快速排序与归并排序的策略有些类似，基本思想也是分治法，首先从待排序列中找一个主元，根据这个主元将待排序列的所有元素划分为两部分，一部分比它小，另一部分比它大，然后对两个子部分在进行划分和排序，依次重复操作，最后再将这些合并为一个序列。基本代码如下：

1
2
3
4
5
6
7
8
void Quick_Sort(ElementType A[], int N) {
	if(N < 2) return;
	pivot = 从A[]中选一个主元;
	将S = {A[] / pivot} 分成2个独立子集;
		A1 = {a ∈ S | A <= pivot};
		A2 = {a ∈ S | A >= pivot};
	A[] = Quick_Sort(A1, N1)∪(pivot)∪Quick_Sort(A2, N2);
}

按照上述的伪码描述，快排需要解决的问题有两个：

1. 如何去选主元
2. 如何进行子集划分

很明显，按照思路，能把第一个问题解决了，第二个问题也就迎刃而解了。

选主元

那么主元应该怎么去选择呢？比较经典的方法就是取头、中、尾三个数（当然也可以五个数）的中位数（以序列{8, 12, 3}为例，它的中位数是8），选主元时，可以顺便将待选的三位数进行排序，这样当选出主元后，也可以待排序列数据的总个数减少，基本代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
ElementType Median3(ElementType A[], int Left, int Right)
{
	int Center = (Left + Right)/2;
	if(A[Left] < A[Center]) Swap(&A[Left], &A[Center]);
	if(A[Left] < A[Right]) Swap(&A[Left], &A[Right]);
	if(A[Center] < A[Right]) Swap(&A[Center], &A[Right]);
	/*after finish swap, A[Left] <= A[Center] <= A[Right]*/
	/*put the pivot to A[Right-1], then only consider the sequence from
	 A[Left+1] to A[Right-2]*/
	Swap(&A[Center], &A[Right-1]);
	return A[Right-1];
}

按照上述代码，因为最后将pivot放到了Right-1位置，所以，另外两个元素的位置就可以不用在考虑了，只考虑区间$[Left+1, Right-1]$内的元素即可。

子集划分

子集划分时，需要使用两个指针，一个首，一个尾，当尾指针小于首指针（两者已交叉）时，说明子集的划分已完成。在进行这个操作时，会存在一个问题，那就是遇到相等的元素怎么办？
以最坏的情况（序列元素全部相等）为例，如果采取直接交换元素的方法，那么首、尾指针的每一次变化，都需要交换一次元素，结束后，主元pivot会被放在中间的位置，这样下一次循环的时候就会将剩下的序列在等分成两个序列，这样时间复杂度就是$O(NlogN)$了；那如果跳过相等的元素呢？在最坏的情况下，会有一端的指针停滞不前，那么每次就只有一个指针在移动，这样每次得到的子序列就$N, N-1, N-2, \dots, 1$了，那样时间复杂度依然是$O(N^2)$，所以还是采取交换元素的方法。
另外，如果数据规模较小的话，，特别是数据总数连100都不到的时候，对于依然使用递归的快速排序而言，就不是那么划算了，所以需要做个判断，在数据规模较小的时候，采取其他的排序方式。

算法实现

选好主元，明确子集的划分方法，就可以来构造算法了，基本代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void QuickSort(ElementType A[], int Left, int Right)
{
	if(Cutoff <= Right-Left){
		Pivot = Median3(A, Left, Right);
		i = Left;
		j = Right - 1;
		for(; ; )
		{
			while(A[++i] < pivot);
			while(A[--j] > pivot);
			if(i < j) Swap(&A[i], &A[j]);
			else break;
		}
		Swap(&A[i], &A[Right-1]);
		QuickSort(A, Left, i-1);
		QuickSort(A, i+1, Right);
	}else Insertion_Sort(A+Left, Right-Left+1);
}

上述代码的思路比较直观，先选好主元，在进行子集划分，然后将主元放到靠近中间的位置，此时主元的位置与最终结果序列的位置是一致的，这点与冒泡排序一样，每次都会有一个元素被排到最终位置。当待排元素小于阈值Cutoff时，直接使用插入排序解决剩下的元素序列。

表排序

表排序适用于待排元素不是简单的整数，而是复杂、庞大的元素的时候，因为这些复杂、庞大的元素的交换和移动会十分费时。也就是说，表排序在排序过程中不需要移动元素，只需要移动指针即可，这种不移动元素，只移动指针的排序方法称为间接排序。
定义一个指针数组作为**“表”（table）**，表排序算法的操作对象就是这个“表”了。

物理排序

假若仍然需要移动实际的元素来完成排序，那么可以根据下面这个结论在线性的时间复杂度内完成这个操作。

定理：N个数字的排列由若干个独立的环组成。

这里的“环”，其实是一个比较抽象的概念，指的是经过表排序后等到的table内，有些元素的顺序会形成一个序列，而这个序列就称作“环”。下面来看个例子，表排序前：

A [0] [1] [2] [3] [4] [5] [6] [7]
key f d c a g b h e
table 0 1 2 3 4 5 6 7
表排序后：
A [0] [1] [2] [3] [4] [5] [6] [7]
key f d c a g b h e
table 3 5 2 1 7 0 4 6
上表中，由{3, 5, 1, 0}这个下标序列可得对应的有序序列为{a, b, d, f}，这个序列是有序的，其对应关系如下表：
A [0] [1] [3] [5]
table 3 5 1 0
由上表中构成的关系，就是“环”，可以根据“环”得到有序的序列。
紧接着，根据这些有序的序列，借助一个临时空间，遍历一次这个有序序列，就可以完成物理序列的排序。很明显可以得到，当table[i] == i时，环就结束了。

时间复杂度分析

当初始序列为有序时，是最好的情况；当有$\lfloor N/2 \rfloor$个环时，每个环包含2个元素，交换两个元素需要三步操作，就需要$\lfloor 3N/2 \rfloor$次元素移动，而表排序针对的就是元素移动时间较长的存储结构，所以时间复杂度为$T = O(m\ N)$，$m$为每个元素的复制时间。

基数排序

基数排序与其他排序算法有一个很大的差别，那就是不仅只是比大小了，因为单纯靠比较大小的排序算法的时间复杂度最低只能是$T(NlogN)$这个级别，所以得在添点“料”来继续提升速度，下面先来看看桶排序。

桶排序

对于桶排序而言，假设待排序列有$N$个元素，先申请$N$个桶（有序，桶内保存指针），然后将每一个符合条件的值，插到这个有序的桶排列中，这样就可以了，大致代码如下：

1
2
3
4
5
6
7
8
9
10
11
void Bucket_Sort(ElementType A[], int N) {
	count[]初始化;
	while(读入一个数据) {
		将该数据插入count[桶内保存的指针++];
	}
	for(i=0; i<M; i++) {
		if(count[i]){
			输出count[i]整个链表;
		}
	}
}

按照上述的伪码，有$N$个数据需要读入，$M$个数据需要输出，所以时间复杂度为$T(N, M) = O(M + N)$。但是当$M >> N$的情况下，使用桶排序就不是那么划算了，这就需要使用基数排序了。

桶排序基本思想

了解了桶排序之后，基数排序就好理解了，基数排序建桶规则是按照给定数据的进制数建桶，例如{78, 123, 44, 678}， 这个序列的数都是十进制的，所以基数（桶的大小）为 10。

基数排序算法的主体思想采用的是次位优先（Least Significant Digit）的思想（也可以使用主位优先(Most Significant Digit)），简单来讲，第一次排序以个位数大小为基准来排序，第二次排序以十位数大小为基准来排序，但需要将第一次排序中的高位数拿出来，重复至最高位排完后结束。每躺排序过程中，需要访问$N$个结点，也需要访问$B$个桶，所以时间复杂度为$T=O(P(N+B))$。

多关键字排序

扑克牌的花色就是一种“多关键字排序”，不同花色同花顺也有大小之分。

以为扑克牌排序为例，扑克牌有两种属性，分别是花色和大小，一副整齐的扑克牌，花色和大小必定都是整齐的，根据基数排序的思想，我们可以先按照大小来做基数排序，这需要13个桶来完成，排好序后，各个桶中的牌的大小都是相等的，此时我们在以花色为基数建桶，依次取出花色按顺序取出花色相同的牌放到不同花色的桶内即可，已经不需要根据大小排序了。

排序算法的比较

排序方法|平均时间复杂度|最坏情况时间复杂度|额外空间复杂度|稳定性
:-: | :-: | :-: | :-: | :-:
简单选择排序 |$O(N^2)$| $O(N^2)$| $O(1)$| 不稳定
冒泡排序 |$O(N^2)$| $O(N^2)$| $O(1)$| 稳定
直接插入排序 |$O(N^2)$| $O(N^2)$| $O(1)$| 稳定
希尔排序 |$O(N^d)$| $O(N^2)$| $O(1)$| 不稳定
堆排序 |$O(NlogN)$| $O(NlogN)$| $O(1)$| 不稳定
快速排序 |$O(NlogN)$| $O(N^2)$| $O(logN)$| 不稳定
归并排序 |$O(NlogN)$| $O(NlogN)$| $O(N)$| 稳定
基数排序 |$O(P(N+B))$| $O(P(N+B))$| $O(N+B)$| 稳定
尽管上表中给出了各排序算法的具体的时间复杂度，但是实际应用时还是需要根据实际情况来选择合适的排序算法。另外，从表中看到堆排序的性能比较好，但是实际效果不太理想。除了这些基础排序算法外，还有很多其他的排序算法，那些也值得进一步学习。

Homework

10-4 统计工龄

这个题目很简单，借助一下姥姥课上讲的桶排序的思想即可，C++ 语法的代码如下：

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
#include <iostream>

int main() {
	int n;
	std::cin >> n;
	int staff[55] = { 0 }, tmp;
	for (int i = 0; i < n; i++) {
		std::cin >> tmp;
		staff[tmp]++;
	}
	for (int i = 0; i < 52; i++) {
		if (staff[i]) std::cout << i << ':' << staff[i] << std::endl;
	}
	return 0;
}

/*
samples:
in:
8
10 2 0 5 7 2 5 2
out:
0:1
2:3
5:2
7:1
10:1

in:
10
10 2 0 0 0 5 7 2 5 2
out:
0:3
2:3
5:2
7:1
10:1
*/

10-5 PAT Judge

这道题目的出题背景应该就是 PAT 的排名系统了，但其实是甲级题库的一道排序题，需要按照题目的要求来进行排序，直接使用 C++ 的库函数会方便许多。

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 10000 + 5;
struct user{
	int id, scores[6], sum, perfect;
	bool flag;
} us[maxn];
int n, k, m, p[6] = {0};
bool cmp(user a, user b) {
	if(a.sum != b.sum) return a.sum > b.sum;
	else if(a.perfect != b.perfect) return a.perfect > b.perfect;
	else return a.id < b.id;
}
void init() {
	for(int i = 1; i <= n; i++) {
		us[i].id = i;
		us[i].sum = us[i].perfect = 0;
		us[i].flag = false;
		memset(us[i].scores, -1, sizeof(us[i].scores));
	}
}
int main() {
	scanf("%d %d %d", &n, &k, &m);
	init();
	for(int i = 1; i <= k; i++) {
		scanf("%d", p + i);
	}
	int id, proid, scoob;
	for(int i = 0; i < m; i++) {
		scanf("%d %d %d", &id, &proid, &scoob);
		if(scoob != -1) us[id].flag = true;
		if(scoob == -1 && us[id].scores[proid] == -1) us[id].scores[proid] = 0;
		if(scoob == p[proid] && us[id].scores[proid] < p[proid]) us[id].perfect++;
		if(scoob > us[id].scores[proid]) us[id].scores[proid] = scoob;
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= k; j++) {
			if(us[i].scores[j] > 0) us[i].sum += us[i].scores[j];
		}
	}
	sort(us + 1, us + n + 1, cmp);
	int rank = 1;
	for(int i = 1; i <= n && us[i].flag; i++) {
		if(i > 1 && us[i].sum != us[i - 1].sum) rank = i;
		printf("%d %05d %d", rank, us[i].id, us[i].sum);
		for(int j = 1; j <= k; j++) {
			if(us[i].scores[j] == -1) printf(" -");
			else printf(" %d", us[i].scores[j]);
		}
		putchar('\n');
	}
	return 0;
} 

/*
samples:
in:
7 4 20
20 25 25 30
00002 2 12
00007 4 17
00005 1 19
00007 2 25
00005 1 20
00002 2 2
00005 1 15
00001 1 18
00004 3 25
00002 2 25
00005 3 22
00006 4 -1
00001 2 18
00002 1 20
00004 1 15
00002 4 18
00001 3 4
00001 4 2
00005 2 -1
00004 2 0
out:
1 00002 63 20 25 - 18
2 00005 42 20 0 22 -
2 00007 42 - 25 - 17
2 00001 42 18 18 4 2
5 00004 40 15 0 25 -

in:
3 4 9
20 25 25 30
00001 3 30
00002 3 30
00003 3 30
00001 3 30
00002 3 20
00003 3 20
00001 3 30
00002 3 10
00003 3 30
out:
1 00001 30 - - 30 -
1 00002 30 - - 30 -
1 00003 30 - - 30 -

in:
2 2 6
20 20
00001 1 -1
00002 1 -1
00001 1 -1
00002 1 -1
00001 1 -1
00002 1 0
out:
(blank)
*/

10-6 Sort with Swap(0, i)

这个题不太好想，但是与表排序非常类似。

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
#include <iostream>
using namespace std;
const int maxn = 100000 + 5;
int pos[maxn], n, ans = 0;
int main() {
    cin >> n;
    int remains = n - 1, tmp;
    for(int i = 0; i < n; i++) {
        cin >> tmp;
        pos[tmp] = i;
        if(tmp == i && tmp != 0) remains--;
    }
    int k = 1;
    while(remains > 0) {
        if(pos[0] == 0) {
            while(k < n) {
                if(pos[k] != k) {
                    swap(pos[0], pos[k]);
                    ans++;
                    break;
                }
                k++;
            }
        }
        while(pos[0] != 0) {
            swap(pos[0], pos[pos[0]]);
            ans++;
            remains--;
        }
    }
    cout << ans;
    return 0;
}

/*
samples:
in:
10
3 5 7 2 6 4 9 0 8 1
out£º
9

in:
5
4 0 2 1 3
out:
3

in:
3
0 2 1
out:
2

in:
5
4 3 2 1 0
out:
4

*/