计数排序
入门最简单的非比较排序，适合值域较小的整数数组。
// 自定义输入
用你自己的数组跑一遍
速度 中
待机 ⌨1void countingSort(int arr[], int n) {
2 int maxVal = *max_element(arr, arr + n);
3 int minVal = *min_element(arr, arr + n);
4 int range = maxVal - minVal + 1;
5 vector<int> count(range, 0), output(n);
6
7 for (int i = 0; i < n; i++)
8 count[arr[i] - minVal]++;
9
10 for (int i = 1; i < range; i++)
11 count[i] += count[i - 1];
12
13 for (int i = n - 1; i >= 0; i--) {
14 output[count[arr[i] - minVal] - 1] = arr[i];
15 count[arr[i] - minVal]--;
16 }
17
18 for (int i = 0; i < n; i++)
19 arr[i] = output[i];
20}
复杂度分析
时间 O(n + k)
空间 O(k)
最优 O(n + k)
最坏 O(n + k)
算法讲解
计数排序先统计数组中每个值出现的次数。
然后按值的顺序依次输出，每个值输出其出现次数那么多。
时间复杂度 O(n + k)，其中 k 是值域范围。
它是基数排序和桶排序的基础，理解非比较排序的关键。