计数排序

• 全称 Counting sort

• 特点

  • 稳定
  • 时间复杂度
    • O(n + w)，其中w代表待排序数据的值域大小,即这些数在哪个区间里面，比如(0，最大值)，其中最大值不要超过上面的W即100010,而且输入不能有负数

• 原理

  • 对nums进行第1次循环(正向)，把当前值当成索引，每出现一次，就让记录数组cnt对应位置的值加1
  • 对记录数组cnt进行 前缀和 叠加操作，目的是得出他们在新数组a中应该呆的位置
  • 对nums进行第2次循环(反向)，并在记录数组cnt中找到其在新数组a中的位置关系，并放入a中
  • 把a交换到nums上面即可
  • 只能用于正数，所以一定要把生成负数的部分注释掉

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

void countingSort(vector<int>& nums) {
    const int W = 100010;
    int cnt[W];
    memset(cnt, 0, sizeof(cnt));
    int len = nums.size();
    vector<int> a(len);
    for(int i = 0; i < len; ++i) ++cnt[nums[i]];
    for(int w = 1; w < W; ++w) cnt[w] += cnt[w - 1];
    for(int i = len - 1; i >= 0; --i) a[--cnt[nums[i]]] = nums[i];
    nums.swap(a);
};

void shuffle(vector<int>& arr) {
    int n = arr.size();
    srand(time(NULL));
    while (n--) {
        const int random = rand() % arr.size();
        swap(arr[n], arr[random]);
    }
}

int main() {
    vector<int> testArr = {5, 7, 3, 4, 2, 6, 1};
    shuffle(testArr);
    countingSort(testArr);
    for(auto e: testArr) cout<<e<<endl;
    return 0;
}