快速排序

#include <bits/stdc++.h>
using namespace std;

int n, a[100010];

void quick_sort(int l, int r) {
    // 当区间内仅剩一个元素时不需要排序
    // r - l + 1 <= 1 等价于 l >= r
    if (l >= r) return ;

    // 随机选取一个pivot
    swap(a[l], a[l + rand() % (r - l + 1)]);
    int x = a[l];

    int i = l, j = r;
    while (i < j) {
        while (i < j && a[j] > x) j--;
        if (i < j) a[i++] = a[j];

        while (i < j && a[i] < x) i++;
        if (i < j) a[j--] = a[i];
    }

    a[i] = x;
    // 递归左子区间
    quick_sort(l, i - 1);
    // 递归右子区间
    quick_sort(i + 1, r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    quick_sort(1, n);

    for (int i = 1; i <= n; i++) cout << a[i] << " ";
    cout << endl;

    return 0;
}

第 $K$ 小的数

#include <bits/stdc++.h>
using namespace std;

int n, k, a[100010];

int quick_select(int l, int r, int k) {
    if (l == r) return a[l];

    swap(a[l], a[l + rand() % (r - l + 1)]);
    int x = a[l];

    int i = l, j = r;
    while (i < j) {
        while (i < j && a[j] > x) j--;
        if (i < j) a[i++] = a[j];

        while (i < j && a[i] < x) i++;
        if (i < j) a[j--] = a[i];
    }

    a[i] = x;

    int rank = i - l + 1;
    if (k == rank) return a[i];
    else if (k < rank) return quick_select(l, i - 1, k);
    else return quick_select(i + 1, r, k - rank);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    cout << quick_select(1, n, k) << endl;

    return 0;
}

归并排序

#include <bits/stdc++.h>
using namespace std;

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

void merge_sort(int l, int r) {
    if (l >= r) return ;

    int mid = l + r >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);

    int i = l, j = mid + 1, k = 1;
    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, k = 1; i <= r; i++, k++) a[i] = temp[k];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    merge_sort(1, n);

    for (int i = 1; i <= n; i++) cout << a[i] << " ";
    cout << endl;

    return 0;
}

逆序对的数量

#include <bits/stdc++.h>
using namespace std;

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

long long merge_sort(int l, int r) {
    if (l >= r) return 0;

    int mid = l + r >> 1;
    long long res = merge_sort(l, mid) + merge_sort(mid + 1, r);

    int i = l, j = mid + 1, k = 1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) temp[k++] = a[i++];
        else {
            // a[i ~ mid] 均与 a[j] 构成逆序对
            res += mid - i + 1;
            temp[k++] = a[j++];
        }
    }

    while (i <= mid) temp[k++] = a[i++];
    while (j <= r) temp[k++] = a[j++];
    for (int i = l, k = 1; i <= r; i++, k++) a[i] = temp[k];

    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    cout << merge_sort(1, n) << endl;

    return 0;
}

计数排序

#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 1000010;

// c[i] 表示 i 出现的次数
// r[i] 表示 i 排序后的位置
int n, m, a[N], c[M], r[M];

void counting_sort() {
    // 排序结果
    for (int i = 1; i <= n; i++) c[a[i]]++;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= c[i]; j++) {
            cout << i << " ";
        }
    }
    cout << endl;

    // 求每个数字的排名
    for (int i = 1; i <= m; i++) c[i] += c[i - 1];
    // 从后往前遍历，保证稳定性
    for (int i = n; i >= 1; i--) r[i] = c[a[i]]--;
    for (int i = 1; i <= n; i++) cout << r[i] << " ";
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        m = max(m, a[i]);
    }

    counting_sort();

    return 0;
}

基数排序

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

// sa[i]: 排序后第 i 小的元素在原始数组 a 中的位置（下标）
// r[i]: 原始数组中第 i 个元素在排序后的位置（排名）
// v[i]: 原始数组中第 i 个元素的当前位数字（用于基数排序）
// c[i]: 计数数组，记录数字 i 出现的次数
int n, m, a[N], sa[N], r[N], v[N], c[10];

void counting_sort() {
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= n; i++) c[v[i]]++;
    for (int i = 1; i <= 9; i++) c[i] += c[i - 1];
    // r[sa[i]] 表示原始位置为 sa[i]的元素在排序后的位置
    for (int i = n; i >= 1; i--) r[sa[i]] = c[v[sa[i]]]--;
    // sa[r[i]] = i 表示：排名为r[i]的元素在原始数组中的位置是i
    for (int i = 1; i <= n; i++) sa[r[i]] = i;
}

void radix_sort() {
    for (int i = 1; i <= n; i++) sa[i] = i;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;

    int t = -1e9;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        t = max(t, a[i]);
    }

    m = 0;
    while (t) {
        t /= 10;
        m++;
    }

    radix_sort();

    for (int i = 1; i <= n; i++) cout << a[sa[i]] << " ";

    return 0;
}