计数排序是一种非比较性质的排序算法，元素从未排序状态变为已排序状态的过程，是由额外空间的辅助和元素本身的值决定的。计数排序过程中不存在元素之间的比较和交换操作，根据元素本身的值，将每个元素出现的次数记录到辅助空间后，通过对辅助空间内数据的计算，即可确定每一个元素最终的位置。
计数排序的核心是....是.....是......是（好吧，小编编不下去了，粘贴辅助过于无节操，大佬实在太过于nb，贴上大佬讲解链接https://www.itcodemonkey.com/article/11750.html）个人觉得理论知识这个讲解的通俗易懂，下边分析代码执行过程：
#include<iostream> #include<vector> using namespace std; void print(vector<int> a) { for (int i = 0; i < a.size(); i++) { cout << a[i] << " "; } cout << endl; } int main() { vector<int> arr{ -1,-5,-6,-2,1,2,8,1,8 }; cout << "未排序数组: "; print(arr); //计数排序 //1.花O（n）时间扫描一下序列，获取max和min int max_value = arr[0], min_value = arr[0]; for (int i = 0; i < arr.size(); i++) { max_value = max_value > arr[i] ? max_value : arr[i]; min_value = min_value > arr[i] ? arr[i] : min_value; } cout << "max_value: " << max_value << " min_value: " << min_value << endl; for (int i = 0; i < arr.size(); i++) { arr[i] -= min_value; } cout << "加上min_value:"; print(arr); //2.开辟一块新的空间创建新的数组 B，长度为 ( max - min + 1) vector<int> count(max_value - min_value +1, 0); 3.数组 B 中 index 的元素记录的值是 A 中某元素出现的次数 for (size_t i = 0; i < arr.size(); i++) { count[arr[i]]++; } cout << "count数组： "; print(count); //4.最后输出目标整数序列，具体的逻辑是遍历数组 B，输出相应元素以及对应的个数 int sort_idx = 0; for (int j = 0; j < count.size(); j++) { while (count[j]>0) { arr[sort_idx] = j + min_value; sort_idx++; count[j]--; } } cout << "排序后： " ; print(arr); system("pause"); }运行结果：
计数排序是一种非基于比较的排序算法，其空间复杂度和时间复杂度均为O(n+k)，其中k是整数的范围。基于比较的排序算法时间复杂度最小是O(nlogn)的。该算法于1954年由 Harold H. Seward 提出；
