全新的排序原理：计数排序
一句话总结
计数排序的原理比较简单：统计每种元素出现的次数，进而推算出每个元素在排序后数组中的索引位置，最终完成排序。
计数排序的时间和空间复杂度都是 O(n+max−min)，其中 n 是待排序数组长度，max−min 是待排序数组的元素范围。
比方说，输入一个 nums 数组，我统计出其中有 2 个元素 1，1 个元素 3，3 个元素 6，那么只要我在数组中依次填入 2 个 1，1 个 3，3 个 6，就能得到排序结果 [1, 1, 3, 6, 6, 6]。
我们做一道简单的题目就能明白了，来看力扣第 75 题「颜色分类」：
这道题有多种思路，最优解法是用双指针技巧仅遍历一次数组完成排序，我会在 数组双指针技巧习题 中介绍。这里我们用计数排序的思路来解决这个问题，说白了就是让你对数组排序，且这个数组里只有 0、1、2 三种元素。
我们可以创建一个大小为 3 的 count 数组，count[0], count[1], count[2] 分别表示数组中 0、1、2 出现的次数。然后我们按照 count 数组的统计结果，依次填充原数组即可。
func sortColors(nums []int) {
// 统计 0, 1, 2 出现的次数
count := make([]int, 3)
for _, element := range nums {
count[element]++
}
// 按照 count 数组的统计结果，依次填充原数组
index := 0
for element := 0; element < 3; element++ {
for i := 0; i < count[element]; i++ {
nums[index] = element
index++
}
}
}
这就是一个简单的计数排序算法，不过这个题目给的场景比较简单，只有 0, 1, 2 三种元素，下面我们给出一个更通用的计数排序算法。
通用的计数排序
虽然计数排序的原理简单，但是在通用的计数排序代码中，还是有一些编码技巧的。
我们从提出问题开始。计数排序需要把数组中的元素作为 count 数组的索引才能计数，那么我们可以提出如下疑问：
1、是不是说只有当 nums 数组中的元素都是非负整数的时候才能用计数排序呢？包含负数时如何排序？对自定义的类型如何排序？
2、根据计数排序的原理，我们仅关心某一个元素出现了多少次，而并不关心相同元素的相对位置，那么看起来计数排序是一个不稳定排序，对吗？
3、因为计数排序需要将元素的值作为 count 数组的索引，那么如果数组中的最大元素的值很大时，会不会导致 count 数组太大，空间复杂度过高？
下面我们来一步一步思考这些问题，尝试给出解法。
处理负数和自定义类型
最简单的计数排序场景就是待排序数组仅包含非负整数，最好这些非负整数还是从 0 开始的。但是我们可以通过简单映射技巧来处理负数和自定义类型。
先说包含负数的情况，比如 nums = [-3, 4, -1, 2, 1]，我们发现其中的最小元素是 -3，那么你就不要直接把 nums[i] 作为 count 数组的索引，而是要把 nums[i] + 3 作为索引，经过 f(i) = nums[i] + 3 这个映射函数，索引就不包含负数了。
对于自定义对象也是类似的，只要你能找到一个映射规则，把对象映射到一个整数，就可以用计数排序了。
说到把任意对象映射为整数索引，有没有很熟悉？有没有联想到 哈希表核心原理 中的 hash 函数？是的，hash 函数也是一个映射规则，但是 hash 函数的特点和计数排序的映射函数的特点是不一样的。
hash 函数有一个关键指标是生成的哈希值要尽量随机，而计数排序的映射函数的关键指标是不能丧失原数据的大小关系。
比方说 nums[i] > nums[j]，显然 nums[i] + 3 > nums[j] + 3 也成立，所以映射函数 f(i) = nums[i] + 3 是可以作为计数排序的映射函数的。
所以，仿照上面的例题代码，我们可以尝试写出如下计数排序算法，给排序算法输入一个映射函数 indexFn，用来把待排序数组中的元素映射到一个非负整数索引：
// 通用的计数排序算法
// indexFn 是映射函数，用来把待排序数组中的元素映射到一个非负整数索引
func sort(nums []int, indexFn func(int) int) {
// 找到最大索引值
int max = 0;
for (int num : nums) {
int index = indexFn(num);
max = max(max, index);
}
// 按照最大索引值决定 count 数组的大小
// 统计每个元素出现的次数
count := make([]int, max+1)
for _, num := range nums {
index := indexFn(num)
count[index]++
}
// 按照 count 数组的统计结果，依次填充原数组
index := 0
for num := 0; num <= max; num++ {
for j := 0; j < count[num]; j++ {
// 这里遇到问题了，因为 num 是经过 indexFn 转换过的值
// 我们需要知道 indexFn 的逆函数，才能还原出原始元素
nums[index] = ???;
index++
}
}
}
代码写到最后会发现问题，因为我们使用 indexFn 函数将原数组中的元素映射到了 0, 1, 2, …, 等非负整数，但是在填充原数组进行排序时，我们必须知道 indexFn 的逆函数，才能还原出原始元素的值。
难道说需要给 sort 函数再加一个参数，传入 indexFn 的逆函数吗？不是不可以，只是还有更好的办法。
累加 count 数组避免使用逆函数 上面的代码写不下去的根本原因，还是因为我们不知道原数组的元素排序后的索引位置。
我们可以通过一个小技巧，不使用逆函数也可以知道原数组的每个元素排序后的位置，那就是累加 count 数组。
count 数组里面本来存储的是 indexFn(nums[i]) 出现的次数；通过累加 count 数组，得到的是 indexFn(nums[i]) 在排序后的数组中的结束位置。
这里我直接举例说明，很容易理解。
假设 nums = [2,3,1,0,2,2,3,0]，都是从零开始的非负整数，所以可以忽略 indexFn 函数，直接用 nums[i] 作为 count 数组的索引，count 数组长这样：
count = [2, 1, 3, 2]
累加 count 数组得到：
count = [2, 3, 6, 8]
现在这个 count 可以如何解释呢？可以这样理解：
count[0] = 2 说明 nums 排序后，索引区间 [0, 2) 都是元素 0；
count[1] = 3 说明 nums 排序后，索引区间 [2, 3) 都是元素 1；
count[2] = 6 说明 nums 排序后，索引区间 [3, 6) 都是元素 2；
count[3] = 8 说明 nums 排序后，索引区间 [6, 8) 都是元素 3。
你可以看看 nums 排序后的结果，确实是这样：
[0, 0, 1, 2, 2, 2, 3, 3]
既然我们现在知道了每个元素在排序后数组中的位置，那么就可以填充数组，完成排序了：
func sort(nums []int, indexFn func(int) int) {
// 找到最大索引值
max := 0
for _, num := range nums {
index := indexFn(num)
if index > max {
max = index
}
}
// 按照最大索引值决定 count 数组的大小
// 统计每个元素出现的次数
count := make([]int, max+1)
for _, num := range nums {
index := indexFn(num)
count[index]++
}
// 累加 count 数组，得到的是 indexFn(nums[i]) 在排序后的数组中的结束位置
for i := 1; i < len(count); i++ {
count[i] += count[i-1]
}
// 根据每个元素排序后的索引位置，完成排序
// 这里注意，我们从后往前遍历 nums，是为了保证排序的稳定性
sorted := make([]int, len(nums))
for i := len(nums) - 1; i >= 0; i-- {
index := indexFn(nums[i])
sorted[count[index]-1] = nums[i]
count[index]--
}
// 把排序结果复制回原数组
for i := 0; i < len(nums); i++ {
nums[i] = sorted[i]
}
}
// 用法示例
nums := []int{2, 3, 1, 0, 2, 2, -4, -1, 3, 0}
sort(nums, func(num int) int { return num + 4 })
fmt.Println(nums)
// [-4 -1 0 0 1 2 2 2 3 3]
注意排序结果需要存到一个新的 sorted 数组中，不能直接存储到 nums 数组，因为计算 index 时还需要 nums[i] 的原始值。
倒序遍历保证排序的稳定性
因为累加 count 数组后，其中存储的是排序后元素的末尾索引，所以 `sorted[count[index] - 1] = nums[i]`; 也是从末尾开始向前填充的。
如果倒序遍历 nums 数组，就能保证排序的稳定性，即相同元素的相对顺序不会改变。
上面这个计数排序算法就比较完善了。不过考虑到做算法题时输入的 nums 一般都是 int[] 数组而不会是自定义类型，所以可以去掉这个 indexFn 参数，直接在算法中计算索引偏移作为映射函数即可：
func sort(nums []int) {
// 找到最大和最小元素
// 计算索引偏移量和 count 数组大小
min, max := nums[0], nums[0]
for _, num := range nums {
if num < min {
min = num
}
if num > max {
max = num
}
}
// 根据最大值和最小值，将元素映射到从 0 开始的索引值
offset := -min
count := make([]int, max-min+1)
// 统计每个元素出现的次数
for _, num := range nums {
count[num+offset]++
}
// 累加 count 数组，得到的是 nums[i] 在排序后的数组中的结束位置
for i := 1; i < len(count); i++ {
count[i] += count[i-1]
}
// 根据每个元素排序后的索引位置，完成排序
// 这里注意，我们从后往前遍历 nums，是为了保证排序的稳定性
sorted := make([]int, len(nums))
for i := len(nums) - 1; i >= 0; i-- {
sorted[count[nums[i]+offset]-1] = nums[i]
count[nums[i]+offset]--
}
// 把排序结果复制回原数组
for i := 0; i < len(nums); i++ {
nums[i] = sorted[i]
}
}
// 用法示例
nums := []int{2, 3, 1, 0, 2, 2, -4, -1, 3, 0}
sort(nums)
这就是一个针对 int[] 数组的通用计数排序算法了，可以处理包含负数的情况。
空间复杂度
现在回答前面提出的第二个问题，如果数组中的元素的值很大时，会不会导致 count 数组太大，空间复杂度过高？
其实根据上面的代码逻辑很容分析出来，count 数组的大小是 max - min + 1，和数组元素的绝对大小无关，只和 max - min 的值，即元素的大小范围有关。
计数排序不是原地排序算法。首先它需要 count 数组辅助，消耗 O(max−min) 的空间复杂度，另外它不能直接把排序结果写到 nums 数组中，还需要一个 sorted 数组存储排序结果，消耗 O(n) 的空间复杂度。
综上，计数排序的空间复杂度是 O(max−min+n)，其中 n 是待排序数组的长度，max−min 是待排序数组的元素范围。
根据选择排序的这个特点，当待排序数组中的极值范围跨度过大时，使用计数排序的空间复杂度会比较高，并不是明智的选择。
时间复杂度
代码中有几个单层 for 循环，分别遍历 nums 数组和 count 数组，所以总的时间复杂度是 O(n+max−min)，其中 n 是待排序数组长度，max−min 是待排序数组的元素范围。
计数排序是一个线性时间复杂度的排序算法，适用于元素范围不大的场景。你可以把上面给出的计数排序算法应用到力扣第 912 题「排序数组」上，可以看到它的性能非常高，也没有出现内存超限的错误，应该可以推断力扣的测试用例中元素范围没有很大。
非比较排序
先别急着找「非比较排序」这个名词的定义，我先提个问题，能否用哈希表替代 count 数组？
这个问题是我当初学习计数排序原理时想到的，把这个问题想明白，就能理解非比较排序的本质了。
比方说 nums = [0, 1000, 1, 1, 1]，这种情况下会创建一个大小为 1001 的 count 数组，但实际上只有 count[0], count[1], count[1000] 存储数据，其他空间都浪费了，这也是计数排序空间复杂度高的根本原因。
那么我们是否可以用哈希表来替代 count 数组，来优化空间复杂度呢？
哈希表核心原理 中介绍过，哈希表本质上就可以看做是一个加强版数组，键就相当于数组索引，值就相当于数组元素。
那么如果换用哈希表来代替 count 数组，上面这个例子，哈希表只需要存储 0, 1, 1000 这三个键值对，就不存在空间浪费了，这是不是一种优化思路？
稍微思考一下，会发现这个思路是不行的。
你有没有发现，前面介绍的 选择排序，插入排序，冒泡排序， 快速排序，归并排序 这些排序算法，都有类似这样的代码：
if (nums[i] > nums[j]) {
...
} else {
...
}
就是说，它们肯定要根据某两个元素的大小关系，然后对这两个元素做一些交换操作。
而计数排序的代码中，你没有看到类似的代码逻辑。如果计数排序都不需要比较元素的大小，那么到底是什么，让他能够完成排序呢？
答案是，它依靠数组索引的有序性，所以不用对元素进行比较。
它把数据映射到 count 数组的索引，这个映射关系保留了原数据的大小关系，又因为 count 的数组索引是单调递增的，所以最后可以通过 count 数组推导出排序后的数组。
因此可知，哈希表不能替代 count 数组，因为哈希表的键并不能像数组索引这样自带有序性，所以无法完成计数排序。
想明白这个道理，就很容易看透非比较排序的本质了。
非比较排序
非比较排序这个名词，从字面上理解，即代码中不包含 `if (nums[i] > nums[j])` 这样的比较逻辑的排序算法。
之所以能不使用比较逻辑，本质在于将原数据映射到一个自带有序性的参考系中（比如数组索引），然后借助这个参考系推导出排序后的结果。
反之，如果待排序的数据不能找到这样一个映射和参考系，则无法使用非比较排序算法。
非比较排序的效率一般都比通用的比较排序要高。比如
快速排序、
归并排序 这种通用排序算法，时间复杂度最快也就是 O(nlogn) 了，而计数排序以及后面介绍到的其他非比较排序算法，在特定场景下的时间复杂度是线性的，性能会显著高于通用排序算法。