排序算法汇总

pAgS9Ve.png

快速排序

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

using namespace std;

const int N = 1e5 + 10;
int n, nums[N];

void qsort(int* a, int l, int r) {
    if(l >= r) return;    // 递归终止条件
    int i = l - 1, j = r + 1;
    int x = a[l + r >> 1];
    while(i < j) {
        do i ++;while(a[i] < x);
        do j --;while(a[j] > x);
        if(i <= j) swap(a[i], a[j]);
    } 
    qsort(a, l, j);
    qsort(a, j + 1, r);
}

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i ++) {
        scanf("%d", &nums[i]);  // 大数据量输入使用scanf更快
    }
    qsort(nums, 0, n - 1);
    for(int i = 0; i < n; i ++) {
        printf("%d ", nums[i]);
    }
    return 0;
}

归并排序

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

using namespace std;

const int N = 1e5 + 10;
int n, nums[N], temp[N];

void merge_sort(int* a, int l, int r) {
    if(l >= r) return ;
    int mid = l + r >> 1;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r) {
        if(a[i] <= a[j]) temp[k ++] = a[i ++];
        else temp[k ++] = a[j ++];
    }
    while(i <= mid) temp[k ++] = a[i ++];
    while(j <= r) temp[k ++] = a[j ++];
    for(int i = l, j = 0; i <= r; i ++) {
        a[i] = temp[j ++];
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 0 ; i < n; i ++) scanf("%d", &nums[i]);
    merge_sort(nums, 0, n - 1);
    for(int i = 0; i < n; i ++) printf("%d ", nums[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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 1e5 + 10;

int h[N], n, m, cnt;

void down(int u) {
    int t = u;
    if(u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(u != t) {
        swap(h[u], h[t]);
        down(t);
    }
}

int main() {
    cin >> n >> m;
    cnt = n;
    for(int i = 1; i <= n; i ++) {
        cin >> h[i];
    }
    for(int i = n / 2; i ; i --) down(i);
    while(m --) {
        cout << h[1] << ' ';
        h[1] = h[cnt --];
        down(1);
    }
    return 0;
}