小鲸鱼的梦境
0%

排序算法

发表于 分类于 Valine：
本文字数： 4.8k 阅读时长 ≈ 4 分钟

前言

记录一下一些基本的排序算法

堆排序

  • 时间复杂度: \(O(n \log n)\)
  • 空间复杂度: \(O(n)\)

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
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

// 交换 a, b 的值
template <typename T>
void swap(T& a, T& b) {
    T c = a;
    a = b;
    b = c;
}

template <typename T>
inline bool comp(T a, T b) {
    // a 在 b 前面返回 true，否则返回 false
    return a < b;
}

// 大顶堆操作：下滤
template <typename T>
inline void percdown(T nums[], int target, int n) {
    int a = target * 2 + 1, b = a + 1, x;
    while (true) {
        x = target;
        if (a < n && comp(nums[x], nums[a])) x = a;
        if (b < n && comp(nums[x], nums[b])) x = b;
        if (x != target)
            swap<T>(nums[x], nums[target]);
        else
            break;
        target = x, a = x * 2 + 1, b = a + 1;
    }
}

// 大顶堆操作：上滤
template <typename T>
inline void percup(T nums[], int target) {
    int f = target - 1 >> 1;
    while (target > 0 && comp(nums[f], nums[target])) {
        swap<T>(nums[f], nums[target]);
        target = f;
        f = target - 1 >> 1;
    }
}

// 对 [0, n) 范围内的数建堆（自底向上构建大顶堆）
template <typename T>
inline void buildheap(T nums[], int n) {
    for (int i = n / 2; i >= 0; --i) {
        percdown<T>(nums, i, n);
    }
}

// 堆排序：对 [0, n) 范围内的数排序
template <typename T>
void heapsort(T nums[], int n) {
    buildheap<T>(nums, n);
    for (int i = n - 1; i > 0; --i) {
        swap(nums[0], nums[i]);
        percdown<T>(nums, 0, i);
    }
}

// -------------------- 测试部分 ---------------------

// 格式化输出数组
void ArrayPrint(int nums[], int n) {
    for (int i = 0; i < n; ++i) {
        printf("%2d ", nums[i]);
    }
    putchar('\n');
}

// 检查数组是否递增有序
bool check_sort(int nums[], int n) {
    for (int i = 1; i < n; ++i) {
        if (nums[i] < nums[i - 1]) return false;
    }
    return true;
}

// 排序检查函数(随机生成长度为1000的数组进行排序并重复1000次)
bool SortTest() {
    freopen("luogu.out", "w", stdout);    // 输出流重定向
    int nums[1007];
    srand((unsigned int)time(NULL));
    for (int i = 0; i < 1000; ++i) {
        for (int j = 0; j < 1000; ++j) {
            nums[i] = rand() % 10000;
            printf("%4d ", nums[i]);
        }
        putchar('\n');

        // 排序函数在这里~~~~~~~~
        heapsort<int>(nums, 1000);
        // quicksort<int>(nums, 0, 999);

        if (!check_sort(nums, 1000)) return false;
        printf("检查通过\n");
    }
    return true;
}

int main() {
    if (SortTest())
        printf("\n排序函数没有问题\n");
    else
        printf("\n排序函数有错误\n");
    return 0;
}

归并算法

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
#include <cstdio>
using namespace std;

// 交换 a, b 的值
template <typename T>
void swap(T& a, T& b) {
    T c = a;
    a = b;
    b = c;
}

// 比较函数
template <typename T>
inline bool comp(T a, T b) {
    return a < b;
}

// 归并: [left, mid - 1], [mid, right)已经有序，将两者合并成一段有序的
template <typename T>
void merge(T nums[], T tmp[], int left, int mid, int right) {
    int i = left, j = mid, k = left;
    while (i < mid && j < right) {
        if (comp(nums[i], nums[j]))
            tmp[k++] = nums[i++];
        else
            tmp[k++] = nums[j++];
    }
    while (i < mid) tmp[k++] = nums[i++];
    while (j < right) tmp[k++] = nums[j++];
    for (k = left; k < right; ++k) nums[k] = tmp[k];
}

// 归并排序主程序：对 [start, end) 范围内的元素进行排序(需要等大的临时空间)
template <typename T>
void mergesort(T nums[], T tmp[], int start, int end) {
    if (start < end - 1) {
        int mid = start + (end - start >> 1);
        mergesort<T>(nums, tmp, start, mid);
        mergesort<T>(nums, tmp, mid, end);
        merge<T>(nums, tmp, start, mid, end);
    }
}

快速排序

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
// 快排模板
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

// 交换 a, b 的值
template <typename T>
void swap(T& a, T& b) {
    T c = a;
    a = b;
    b = c;
}

// 比较函数
template <typename T>
inline bool comp(T a, T b) {
    // a 在 b 前面返回 true，否则返回 false
    return a < b;
}

// 对 [start, end] 范围内的函数进行快速排序
template <typename T = int>
void quicksort(T nums[], int start, int end) {
    if (start >= end)
        return;
    else if (start + 1 == end) {
        if (!comp(nums[start], nums[end]))
            swap(nums[start], nums[end]);
    }
    else {
        int idx = rand() % (end - start + 1) + start;
        swap(nums[start], nums[idx]);
        int left = start, right = end;
        while (left < right) {
            while (left < right && !comp(nums[right], nums[start])) right--;
            while (left < right && !comp(nums[start], nums[left])) left++;
            if (left < right)
                swap(nums[left], nums[right]);
            else
                break;
        }
        swap(nums[start], nums[left]);
        quicksort<T>(nums, start, left - 1);
        quicksort<T>(nums, left + 1, end);
    }
}

int n, t;
int nums[100007];

int main() {
    // freopen("luogu.in", "r", stdin);      // 输入流重定向
    // freopen("luogu.out", "w", stdout);    // 输出流重定向

    srand((unsigned)time(0));

    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &t);
        nums[i] = t;
    }
    quicksort(nums, 0, n - 1);
    for (int i = 0; i < n; ++i) {
        printf("%d ", nums[i]);
    }

    return 0;
}
--- ♥ end ♥ ---

欢迎关注我呀~