## 计数排序 1. 基本思想：计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键值存储在额外开辟的数组空间中。作为一种线性时间复杂度的算法，计数排序要求输入的数据必须是有确定范围的整数。 ``` void countingSort(vector<int>& data) { int min = data[0]; int max = data[0]; for (auto x : data) { if (x < min) min = x; if (x > max) max = x; } int dis = 0 - min; // 0和min偏移的长度，后续data数组元素值x+dis即对应bucket的索引 vector<int> bucket = vector<int>(max - min + 1, 0); for (auto x : data) { bucket[x + dis]++; } int index = 0; int i = 0; while (index < data.size()) { if (bucket[i] != 0) { data[index++] = i - dis; bucket[i]--; } else { i++; } } } ```