排序算法

sort

基础

sort(a + l, a + r + 1); //按小于号规则排序
sort(a + l, a + r + 1, cmp); //用 cmp(a,b) 替代 a < b
sort(a.begin(), a.end());// vector

例子

cmp 写法

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n;
struct Stu
{
    string nam;
    int score;
    int id;
};
Stu a[MAXN + 5];
bool cmp(Stu x, Stu y)
{
    if (x.score != y.score)
        return x.score > y.score;
    return x.id < y.id;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].nam >> a[i].score;
        a[i].id = i;
    }
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++)
        cout << a[i].nam << " " << a[i].score << "\n";
    return 0;
}

重载运算符

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n;
struct Stu
{
    string nam;
    int score;
    int id;
};
bool operator<(const Stu &a, const Stu &b)
{
    if (a.score != b.score)
        return a.score > b.score;
    return a.id < b.id;
}
Stu a[MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].nam >> a[i].score;
        a[i].id = i;
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
        cout << a[i].nam << " " << a[i].score << "\n";
    return 0;
}

另一种重载运算符写法

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n;
struct Stu
{
    string nam;
    int score;
    int id;
    bool operator<(const Stu &b) const
    {
        if (score != b.score)
            return score > b.score;
        return id < b.id;
    }
};
Stu a[MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].nam >> a[i].score;
        a[i].id = i;
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
        cout << a[i].nam << " " << a[i].score << "\n";
    return 0;
}

经典下标排序

#include <bits/stdc++.h>
using namespace std;
int n;
int a[1005];
int id[1005];
bool cmp(int x, int y)
{
    if (a[x] != a[y])
        return a[x] < a[y];
    return x < y;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        id[i] = i;
    }
    sort(id + 1, id + n + 1, cmp);
    for (int i = 1; i <= n; i++)
        cout << id[i] << " ";
    return 0;
}

简单排序

选择排序

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n;
string nam[MAXN + 5];
int score[MAXN + 5];
int id[MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> nam[i] >> score[i];
        id[i] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            if (score[j] > score[i] ||
                score[j] == score[i] && id[j] < id[i])
            {
                swap(nam[i], nam[j]);
                swap(score[i], score[j]);
                swap(id[i], id[j]);
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        cout << nam[i] << " " << score[i] << "\n";
    }
    return 0;
}

冒泡排序

最优化写法：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n;
struct Stu
{
    string nam;
    int score, id;
};
Stu a[MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].nam >> a[i].score;
        a[i].id = i;
    }
    for (int i = 1; i <= n - 1; i++)
    {
        bool flag = false;
        for (int j = 1; j <= n - i; j++)
            if (a[j + 1].score > a[j].score)
                swap(a[j], a[j + 1]), flag = true;
        if (!flag)
            break;
    }
    for (int i = 1; i <= n; i++)
    {
        cout << a[i].nam << " " << a[i].score << "\n";
    }
    return 0;
}

插入排序

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n;
struct Stu
{
    string nam;
    int score, id;
};
Stu a[MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].nam >> a[i].score;
        a[i].id = i;
    }
    for (int i = 2; i <= n; i++)
        for (int j = i; j > 1 && a[j].score > a[j - 1].score; j--)
            swap(a[j], a[j - 1]);
    for (int i = 1; i <= n; i++)
    {
        cout << a[i].nam << " " << a[i].score << "\n";
    }
    return 0;
}

多关键字计数排序

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n;
struct Stu
{
    string nam;
    int score;
};
Stu a[MAXN + 5];
Stu b[MAXN + 5];
int cnt[751];
int sum[751]; // 不包括自己后缀和（有几个人比这个分数高）
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].nam >> a[i].score;
    for (int i = 1; i <= n; i++)
        cnt[a[i].score]++;
    sum[750] = 0;
    for (int i = 749; i >= 0; i--)
        // (>i) = (>i+1) + (==i+1)
        sum[i] = sum[i + 1] + cnt[i + 1];
    for (int i = 1; i <= n; i++)
    {
        // 先看看有几个人比 a[i] 分数高：sum[a[i].score]
        // 算出来 a[i] 的排名：sum[a[i].score] + 1
        // 把 a[i] 放到 b 数组的这个位置
        b[sum[a[i].score] + 1] = a[i];
        // 后面同样分数的人，排名要往后挪一位
        sum[a[i].score] += 1;
    }
    for (int i = 1; i <= n; i++)
        cout << b[i].nam << " " << b[i].score << "\n";

    return 0;
}

高级排序

快速排序

模板

// 对 a[L] ~ a[R] 排序
mt19937 rnd(time(0));
void quick_sort(int a[], int L, int R)
{
    if (L >= R)
        return;
    // 挑选key
    int pos = rnd() % (R - L + 1) + L;
    swap(a[L], a[pos]);
    int key = a[L];
    // 把序列划分成两部分
    int i = L;
    int j = R;
    while (i < j)
    {
        while (j > i && a[j] >= key)
            j--;
        a[i] = a[j];
        while (i < j && a[i] <= key)
            i++;
        a[j] = a[i];
    }
    a[i] = key;
    // 对两部分分别排序
    quick_sort(a, L, i - 1);
    quick_sort(a, i + 1, R);
}

额外应用

#include <bits/stdc++.h>
using namespace std;
// 对 a[L] ~ a[R] 排序，保证 a[k] 的位置是正确的
mt19937 rnd(time(0));
void kth(int a[], int L, int R, int k)
{
    if (L >= R)
        return;
    // 挑选key
    int pos = rnd() % (R - L + 1) + L;
    swap(a[L], a[pos]);
    int key = a[L];
    // 把序列划分成两部分
    int i = L;
    int j = R;
    while (i < j)
    {
        while (j > i && a[j] <= key)
            j--;
        a[i] = a[j];
        while (i < j && a[i] >= key)
            i++;
        a[j] = a[i];
    }
    a[i] = key;
    // 看看还要怎么排
    // L~i-1   i    i+1~R
    if (i == k)
        return;
    else if (k < i)
        kth(a, L, i - 1, k);
    else
        kth(a, i + 1, R, k);
}
const int MAXN = 1000000;
int n, k;
int a[MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    kth(a, 1, n, k);
    cout << a[k];
    return 0;
}

STL 中的 nth_element

nth_element(a + 1, a + k, a + n + 1, cmp);

归并排序

模板

const int MAXN = 1000000;
int n;
int a[MAXN + 5];
int temp[MAXN + 5];
void merge_array(int L, int R)
{
    int M = (L + R) / 2;
    // L ~ M  :  M+1 ~ R
    int pl = L, pr = M + 1;
    int pt = L;
    // 两边都还有东西，就比较
    while (pl <= M && pr <= R)
    {
        if (a[pl] <= a[pr])
            temp[pt++] = a[pl++];
        else
            temp[pt++] = a[pr++];
    }
    while (pl <= M)
        temp[pt++] = a[pl++];
    while (pr <= R)
        temp[pt++] = a[pr++];
    // 放回到 a 数组
    for (int i = L; i <= R; i++)
        a[i] = temp[i];
}
void merge_sort(int L, int R)
{
    if (L >= R)
        return;
    int M = (L + R) / 2;
    merge_sort(L, M);
    merge_sort(M + 1, R);
    merge_array(L, R);
}

额外应用

选择右边元素时，左边剩余元素形成的逆序对都被消除了

...
    if (a[pl] <= a[pr])
            temp[pt++] = a[pl++];
        else
            temp[pt++] = a[pr++], ans += M - pl + 1;
... 

堆排序

模板

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000;
int n;
int a[MAXN + 5];
int tot; // 当前堆大小 a[1]~a[tot]
void up(int pos)
{
    while (pos != 1 && a[pos] > a[pos / 2])
    {
        swap(a[pos], a[pos / 2]);
        pos = pos / 2;
    }
}
void down(int pos)
{
    while (1)
    {
        int maxPos = pos;
        if (pos * 2 <= tot && a[pos * 2] > a[maxPos])
            maxPos = pos * 2;
        if (pos * 2 + 1 <= tot && a[pos * 2 + 1] > a[maxPos])
            maxPos = pos * 2 + 1;
        if (maxPos != pos)
        {
            swap(a[pos], a[maxPos]);
            pos = maxPos;
        }
        else
            break;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 2; i <= n; i++)
        up(i);
    tot = n;
    for (int i = 1; i <= n - 1; i++)
    {
        swap(a[1], a[tot]);
        tot--;
        down(1);
    }
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
    return 0;
}

额外应用

        if (op == 1)
        {
            a[++tot] = x;
            up(tot);
        }
        if (op == 2)
            cout << a[1] << "\n";
        if (op == 3)
        {
            swap(a[1], a[tot]);
            tot--;
            down(1);
        }