排序算法模板.md

发表于 阅读次数：

排序算法模板分享

虽然实际CP竞赛中不会让你手写排序，但是学习一下一些排序算法的思想还是有些用处。

如果你用的是C++，可以使用算法库 <algorithm.h> 里的 std::sort() 快速对数组进行排序。

e.g.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>

using namespace std;

int main() {
    vector<int> vec = {5, 4, 3, 2, 1};
    sort(vec.begin(), vec.end());

    for (auto v : vec) {
        cout << v << " ";
    }

    return 0;
}

运行结果是:

1
1 2 3 4 5

快速排序

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
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 10;
int n;
int arr[MAXN];

void quick_sort(int arr[], int l, int r) {
    int x = arr[(l + r) >> 1], i = l - 1, j = r + 1;
    if (l >= r) return ;
    while (i < j) {
        do i++; while (arr[i] < x);
        do j--; while (arr[j] > x);
        if (i < j) swap(arr[i], arr[j]);
    }
    quick_sort(arr, l, j);
    quick_sort(arr, j + 1, r);
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    quick_sort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[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
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 10;
int arr[MAXN];
int n;

void merge_sort(int arr[], int l, int r) {
    if (l >= r) return ;
    int mid = (l + r) >> 1, i = l, j = mid + 1, k = 0;

    merge_sort(arr, l, mid), merge_sort(arr, mid + 1, r);

    int tmp[MAXN];

    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
        else tmp[k++] = arr[j++];
    }
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= r) tmp[k++] = arr[j++];

    for (i = l, j = 0; i <= r; i++, j++) {
        arr[i] = tmp[j];
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    merge_sort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}