无需比较的排序

非比较排序利用整数值域、数字位或数据分布确定位置，因此不受比较排序 O(n log n) 下界约束；代价是只能用于满足特定条件的数据，并常需要额外空间。

计数排序

统计每个值出现次数，再对计数做前缀和。前缀和表示该值在有序序列中的结束位置；从原数组从后向前放入输出数组，可以保持稳定性。若值域为 k=max-min+1，时间 O(n+k)、空间 O(n+k)。含负数时以 x-min 作为计数下标。

vector<int> countSort(const vector<int>& a) {
    int mn = *min_element(a.begin(), a.end());
    int mx = *max_element(a.begin(), a.end());
    vector<int> cnt(mx - mn + 1), out(a.size());
    for (int x : a) ++cnt[x - mn];
    for (int i = 1; i < (int)cnt.size(); ++i) cnt[i] += cnt[i - 1];
    for (int i = (int)a.size() - 1; i >= 0; --i)
        out[--cnt[a[i] - mn]] = a[i];
    return out;
}

桶排序

桶排序按映射规则把数据分入多个桶，分别排序后按桶序合并。数据均匀分布时平均可达 O(n+k)，若大量数据落入同一桶，桶内排序可能退化到 O(n²)。桶的划分规则和桶内排序方法决定实际性能。

基数排序

基数排序按个位、十位等从低位到高位依次排序（LSD），每一轮必须使用稳定排序，常以计数排序实现；否则先处理的低位次序会被破坏。对于 n 个 d 位、基数为 r 的整数，复杂度为 O(d(n+r))，空间通常为 O(n+r)。

当值域远大于数据量时，计数数组会浪费内存；此时应考虑比较排序或先做离散化。