全新的排序原理：计数排序

比方说，输入一个 nums 数组，我统计出其中有 2 个元素 1，1 个元素 3，3 个元素 6，那么只要我在数组中依次填入 2 个 1，1 个 3，3 个 6，就能得到排序结果 [1, 1, 3, 6, 6, 6]。

我们做一道简单的题目就能明白了，来看力扣第 75 题「颜色分类」：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

输入：nums = [2,0,1]
输出：[0,1,2]

这道题有多种思路，最优解法是用双指针技巧仅遍历一次数组完成排序，我会在 数组双指针技巧习题 中介绍。这里我们用计数排序的思路来解决这个问题，说白了就是让你对数组排序，且这个数组里只有 0、1、2 三种元素。

我们可以创建一个大小为 3 的 count 数组，count[0], count[1], count[2] 分别表示数组中 0、1、2 出现的次数。然后我们按照 count 数组的统计结果，依次填充原数组即可。

class Solution {
    public void sortColors(int[] nums) {
        // 统计 0, 1, 2 出现的次数
        int[] count = new int[3];
        for (int element : nums) {
            count[element]++;
        }

        // 按照 count 数组的统计结果，依次填充原数组
        int index = 0;
        for (int element = 0; element < 3; element++) {
            for (int i = 0; i < count[element]; i++) {
                nums[index] = element;
                index++;
            }
        }
    }
}

class Solution {
public:
    void sortColors(vector<int>& nums) {
        // 统计 0, 1, 2 出现的次数
        vector<int> count(3, 0);
        for (int element : nums) {
            count[element]++;
        }

        // 按照 count 数组的统计结果，依次填充原数组
        int index = 0;
        for (int element = 0; element < 3; element++) {
            for (int i = 0; i < count[element]; i++) {
                nums[index] = element;
                index++;
            }
        }
    }
};

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        # 统计 0, 1, 2 出现的次数
        count = [0] * 3
        for element in nums:
            count[element] += 1

        # 按照 count 数组的统计结果，依次填充原数组
        index = 0
        for element in range(3):
            for _ in range(count[element]):
                nums[index] = element
                index += 1

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++
        }
    }
}

var sortColors = function(nums) {
    // 统计 0, 1, 2 出现的次数
    const count = [0, 0, 0];
    for (const element of nums) {
        count[element]++;
    }

    // 按照 count 数组的统计结果，依次填充原数组
    let index = 0;
    for (let element = 0; element < 3; element++) {
        for (let i = 0; i < count[element]; i++) {
            nums[index] = element;
            index++;
        }
    }
};

这就是一个简单的计数排序算法，不过这个题目给的场景比较简单，只有 0, 1, 2 三种元素，下面我们给出一个更通用的计数排序算法。

通用的计数排序

虽然计数排序的原理简单，但是在通用的计数排序代码中，还是有一些编码技巧的。

我们从提出问题开始。计数排序需要把数组中的元素作为 count 数组的索引才能计数，那么我们可以提出如下疑问：

1、是不是说只有当 nums 数组中的元素都是非负整数的时候才能用计数排序呢？包含负数时如何排序？对自定义的类型如何排序？

2、根据计数排序的原理，我们仅关心某一个元素出现了多少次，而并不关心相同元素的相对位置，那么看起来计数排序是一个不稳定排序，对吗？

3、因为计数排序需要将元素的值作为 count 数组的索引，那么如果数组中的最大元素的值很大时，会不会导致 count 数组太大，空间复杂度过高？

下面我们来一步一步思考这些问题，尝试给出解法。