排序算法的比较（随机化快速排序）

发表于

给定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 -