排序总结

wh2011 · 2023-11-05 13:09:13 · 个人记录

基数排序

#include <bits/stdc++.h>
#include <cstdio>
#define rep(x, y, z) for (int x = y; x <= z; ++x)
#define per(x, y, z) for (int x = y; x >= z; --x)
#define mem(a, x) memset(a, x, sizeof a)
#define ios ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all() x.begin(), x.end()
#define x first
#define y second
#define swap(a, b) a = a ^ b, b = b ^ a, a = a ^ b
#define pd push_back
#define endl '\n'
#define il inline
using namespace std;
using ll = long long;
using db = double;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
int rd() {int s = 0, fu = 1; char ch = getchar(); while (ch < '0' || ch > '9') {if (ch == '-') fu = -1; ch = getchar();} while (ch >= '0' && ch <= '9') {s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar();} return s * fu;}
void rt(int x) {int sta[20], tt = 0; if (x < 0) putchar('-'), x = -x; do sta[tt++] = x % 10, x /= 10; while (x); while (tt) putchar(sta[--tt] ^ 48);}
void sao(int x) {rt(x); putchar(' ');}
void wao(int x) {rt(x); putchar('\n');}
int qmi(ll a, int b) {ll res = 1; while (b) {if (b & 1) res = res * a; a = a * a; b >>= 1;} return res;}
int qmi(ll a, int b, int p) {ll res = 1 % p; while (b) {if (b & 1) res = res * a % p; a = a * a % p; b >>= 1;} return res;}

const int N = 1e5 + 10;
int n, m, a[N], sa[N], c[10], r[N], v[N];

void countingsort() {
    memset(c, 0, sizeof c);
    for (int i = 1; i <= n; ++i) {
        ++c[v[i]];
    }
    for (int i = 1; i < 10; ++i)
        c[i] += c[i - 1];
    for (int i = n; i; --i) {
        r[sa[i]] = c[v[sa[i]]]--;
    }
    for (int i = 1; i <= n; ++i)
        sa[r[i]] = i;
}

void radixsort() {
    for (int i = 1; i <= n; ++i) {
        sa[i] = i;
    }
    for (int i = 1, x = 1; i <= m; ++i, x *= 10) {
        for (int j = 1; j <= n; ++j) {
            v[j] = a[j] / x % 10;
        }
        countingsort();
    }
}

int get(int x) {
    int ans = 0;
    do ++ans, x /= 10; while (x);
    return ans;
}

int main() {
    n = rd();
    for (int i = 1; i <= n; ++i) {
        a[i] = rd();
        m = max(m, get(a[i]));
    }
    radixsort();
    for (int i = 1; i <= n; ++i)
        sao(a[sa[i]]);
    return 0;
}

快速排序

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int q[N];

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

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        scanf("%d", &q[i]);
    quick_sort(q, 0, n - 1);
    for (int i = 0; i < n; i ++ )
        printf("%d ", q[i]);
    printf("\n");
    return 0;
}

归并排序

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n, a[100010],tmp[100010];

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

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
        scanf("%d", &a[i]);
    mysort(1, n);
    for (int i = 1; i <= n; i ++ )
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}