计数排序

计数排序的原理比较简单：统计每种元素出现的次数，进而推算出每个元素在排序后数组中的索引位置，最终完成排序。

想法

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

看个题目就明白了 颜色分类

---

75. 颜色分类 | 力扣 | LeetCode | 🟠
    给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

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

输出：[0,0,1,1,2,2]

示例 2：

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

输出：[0,1,2]

提示：

n == nums.length

1 <= n <= 300

nums[i] 为 0、1 或 2

进阶：

你能想出一个仅使用常数空间的一趟扫描算法吗？

---

我们用计数排序的思路来解决这个问题，说白了就是让你对数组排序，且这个数组里只有 0、1、2 三种元素。

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

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

这样一来，我们就完成了颜色分类问题的排序。