排序——计数排序

计数排序是一种稳定的排序方法，它能在线性时间$O(n + k)$内对包含$n$个元素的数组进行排序，其中数组元素均大于等于0且小于等于$k$。

• ALDS1_6_A: Counting Sort

#include <bits/stdc++.h>

using namespace std;

vector<int> tmp(10005, 0);
vector<int> seq(2 * 1e6 + 5), help(2 * 1e6 + 5);
int n, maxNum = 0;

ostream & operator<<(ostream & os, const vector<int> & v)
{
    for (int i = 1; i <= n; ++i) {
        os << v[i];
        if (i != n) os << ' ';
    }
    os << endl;
    return os;
}

void countingSort()
{
    //统计每个数字出现的次数
    for (int i = 0; i < n; ++i) ++tmp[seq[i]];

    //统计小于等于i的数字的个数
    for (int i = 1; i <= maxNum; ++i) tmp[i] += tmp[i - 1];

    //数值写入排序后的数组help,倒序保证稳定性
    for (int i = n - 1; i >= 0; --i) {
        help[tmp[seq[i]]] = seq[i];
        --tmp[seq[i]];
    }
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> seq[i];
        maxNum = max(maxNum, seq[i]);
    }
    countingSort();
    cout << help;

    return 0;
}