排序算法的比较(随机化快速排序)

给定N个(长整型范围内的)整数,要求输出从小到大排序后的结果。

本题旨在测试各种不同的排序算法在各种数据情况下的表现。

各组测试数据特点如下:

数据1:只有$1$个元素;

数据2:$11$个不相同的整数,测试基本正确性;

数据3:$10^3$个随机整数;

数据4:$10^4$个随机整数;

数据5:$10^5$个随机整数;

数据6:$10^5$个顺序整数;

数据7:$10^5$个逆序整数;

数据8:$10^5$个基本有序的整数;

数据9:$10^5$个随机正整数,每个数字不超过$1000$。

输入格式:

输入第一行给出正整数N(≤$10^5$),随后一行给出$N$个(长整型范围内的)整数,其间以空格分隔。

输出格式:

在一行中输出从小到大排序后的结果,数字间以1个空格分隔,行末不得有多余空格。

输入样例:

1
2
11
4 981 10 -17 0 -20 29 50 8 43 -5

输出样例:

1
-20 -17 -5 0 4 8 10 29 43 50 981

Source Code (C Language)

Quick Sort

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
#include<stdio.h>
#define maxN 100000
//Quick Sort
void swap(long int* a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
int Partition(long int* a, int p, int r) {
int x = a[r];
int i = p - 1;
for (int j = p; j < r; j++) {
if (a[j] <= x) {
i++;
swap(a, i, j);
}
}
swap(a, i + 1, r);
return i + 1;
}
void QuickSort(long int* a, int p, int r) {
if (p < r) {
int q = Partition(a, p, r);
QuickSort(a, p, q - 1);
QuickSort(a, q + 1, r);
}
}
int main() {
int N, i;
long int data[maxN];
if (NULL == scanf("%d", &N)) {
return;
}
for (i = 0; i < N; i++) {
if (NULL == scanf("%ld", &data[i])) {
return;
}
}
QuickSort(data, 0, N - 1);
for (i = 0; i < N; i++) {
i == N - 1 ? printf("%d", data[i]) : printf("%d ", data[i]);
}
return 0;
}

快速排序有着众所周知的缺点:如果在算法的每一层递归上,划分都是最大程度不平衡的,那么算法的时间复杂度就是O(n^2)。也就是说,在最坏情况下,快速排序算法的运行时间并不比插入排序更好,此外,当输入数组完全有序时,快速排序的时间复杂度仍然为O(n^2).

Randomized Quick Sort

快速排序对于有顺序的数字序列表现较差,参考《算法导论》对快速排序进行优化,即快速排序的随机化版本如下:通过显式地对输入进行重新排列,使得算法实现随机化。具体思路为将主元(一般为数组末尾的数字)与数组中随机一个数字进行交换,这样保证了主元是随机选取的。

与上文快速排序相比仅两处改动

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
#include<stdio.h>
#include<stdlib.h>
#define maxN 100000
//Quick Sort
void swap(long int* a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}

int Partition(long int* a, int p, int r) {
int x = a[r];
int i = p - 1;
for (int j = p; j < r; j++) {
if (a[j] <= x) {
i++;
swap(a, i, j);
}
}
swap(a, i + 1, r);
return i + 1;
}

//random
//先进行一步交换,再继续
int Randomized_Partition(long int* a, int p, int r) { //改动1:新函数Randomized_Partition()
int i = rand() % (r - p + 1) + p;
swap(a, i, r);
return Partition(a, p, r);
}

void QuickSort(long int* a, int p, int r) {
if (p < r) {
int q = Randomized_Partition(a, p, r); //改动2:调用新函数
QuickSort(a, p, q - 1);
QuickSort(a, q + 1, r);
}
}

int main() {
int N, i;
long int data[maxN];
long int T[maxN];
if (NULL == scanf("%d", &N)) {
return;
}
for (i = 0; i < N; i++) {
if (NULL == scanf("%ld", &data[i])) {
return;
}
}
QuickSort(data, 0, N-1);
for (i = 0; i < N; i++) {
i == N - 1 ? printf("%d", data[i]) : printf("%d ", data[i]);
}
return 0;
}

对比标准快速排序,对有序数组的效率有了极大的提升。

Heap Sort

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
#include<stdio.h>
#define maxN 100000
//HeapSort

int left(int x) {
return 2 * x + 1;
}
int right(int x) {
return 2 * x + 2;
}
int father(int x) {
return (x - 1) / 2;
}
void swap(long int* array, int x, int y) {
int t = array[x];
array[x] = array[y];
array[y] = t;
}
void MaxHeapify(long int* array, int i, int HeapSize) {
int max, l, r;
l = left(i);
r = right(i);
if (l < HeapSize && array[i] <= array[l]) {
max = l;
}
else {
max = i;
}
if (r < HeapSize && array[max] <= array[r]) {
max = r;
}
if (max != i) {
swap(array, max, i);
MaxHeapify(array, max, HeapSize);
}
}
void buildMaxHeap(long int* array, int N) {
for (int i = (N - 1) / 2; i >= 0; i--) {
MaxHeapify(array, i, N);
}
}
void HeapSort(long int* array, int N) {
int HeapSize = N;
buildMaxHeap(array, N);
for (int i = 0; i < N; i++) {
swap(array, 0, HeapSize - 1);
MaxHeapify(array, 0, --HeapSize);
}
}
int main() {
int N, i;
long int data[maxN];
if (NULL == scanf("%d", &N)) {
return;
}
for (i = 0; i < N; i++) {
if (NULL == scanf("%ld", &data[i])) {
return;
}
}
HeapSort(data, N);
for (i = 0; i < N; i++) {
i == N - 1 ? printf("%d", data[i]) : printf("%d ", data[i]);
}
return 0;
}

Merge Sort

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<stdio.h>
#define maxN 100000
//MergeSort
void MergeSort(long int* a, int x, int r, long int* T) {
if (r - x > 1) {
int m = (x + r) / 2;
int i = x, q = m, p = x;
MergeSort(a, x, m, T);
MergeSort(a, m, r, T);
while (p < m || q < r) {
if (q >= r || (p < m && a[p] <= a[q]))
T[i++] = a[p++];
else
T[i++] = a[q++];
}
for (i = x; i < r; i++) {
a[i] = T[i];
}
}
}
int main() {
int N, i;
long int data[maxN];
long int T[maxN];
if (NULL == scanf("%d", &N)) {
return;
}
for (i = 0; i < N; i++) {
if (NULL == scanf("%ld", &data[i])) {
return;
}
}
MergeSort(data, 0, N, T);
for (i = 0; i < N; i++) {
i == N - 1 ? printf("%d", data[i]) : printf("%d ", data[i]);
}
return 0;
}

Insertion Sort

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
#include<stdio.h>
#define maxN 100000
//Insertion Sort
void InsertionSort(long int* a, int N) {
int i, j, k;
for (i = 1; i < N; i++) {
k = a[i];
j = i - 1;
while (j >= 0 && a[j] > k) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = k;
}
}
int main() {
int N, i;
long int data[maxN];
long int T[maxN];
if (NULL == scanf("%d", &N)) {
return;
}
for (i = 0; i < N; i++) {
if (NULL == scanf("%ld", &data[i])) {
return;
}
}
InsertionSort(data, N);
for (i = 0; i < N; i++) {
i == N - 1 ? printf("%d", data[i]) : printf("%d ", data[i]);
}
return 0;
}

Bubble Sort

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
#include<stdio.h>
#include<stdlib.h>
#define maxN 100000
//BubbleSort
void BubbleSort(long int* a, int N) {
int i, j;
for (i = 0; i < N; i++) {
for (j = 1; j < N - i; j++) {
if (a[j - 1] > a[j]) {
int t = a[j - 1];
a[j - 1] = a[j];
a[j] = t;
}
}
}
}
int main() {
int N, i;
long int data[maxN];
long int T[maxN];
if (NULL == scanf("%d", &N)) {
return;
}
for (i = 0; i < N; i++) {
if (NULL == scanf("%ld", &data[i])) {
return;
}
}
BubbleSort(data, N);
for (i = 0; i < N; i++) {
i == N - 1 ? printf("%d", data[i]) : printf("%d ", data[i]);
}
return 0;
}

总结

对于以上六种排序算法的耗时统计如下表:(单位:ms)

测试点 \ 排序算法 快排 随机快排 归并 堆排 插入 冒泡
0:只有1个元素 1 2 2 1 1 1
1:11个不相同的整数,测试基本正确性 1 2 2 1 1 1
2:10^3个随机整数 2 2 2 2 3 3
3:10^4个随机整数 4 4 7 6 29 170
4:10^5个随机整数 27 28 52 52 1829 >10000
5:10^5个顺序整数 5376 45 44 47 29 5181
6:10^5个逆序整数 4462 41 43 47 3771 >10000
7:10^5个基本有序的整数 5060 42 44 48 36 5102
8:10^5个随机正整数,每个数字不超过1000 28 31 48 48 1829 >10000

对于以上六种排序算法的内存占用统计如下表:(单位:KB)

测试点 \ 排序算法 快排 随机快排 归并 堆排 插入 冒泡
0:只有1个元素 228 384 196 384 256 384
1:11个不相同的整数,测试基本正确性 224 380 296 256 256 368
2:10^3个随机整数 360 228 364 384 288 296
3:10^4个随机整数 352 384 384 408 384 384
4:10^5个随机整数 1664 1664 2304 1664 1612 -
5:10^5个顺序整数 6340 1664 2304 1636 1696 1596
6:10^5个逆序整数 3928 1536 2404 1704 1664 -
7:10^5个基本有序的整数 6048 1636 2432 1704 1664 1592
8:10^5个随机正整数,每个数字不超过1000 1440 1496 2148 1408 1440 -