计数排序 题目描述：给定一个包含 n 个非负整数的数组，数组中的每个元素的值都在 0 到 k 的范围内（k 是一个整数）。请设计一个算法，将这个数组按升序排序。要求算法的时间复杂度为 O(n + k)，空间复杂度为 O(n + k)。 解题过程： 理解算法核心思想 计数排序不是一种基于比较的排序算法（如快速排序、归并排序）。它的核心思想是：对于每个输入元素 x，确定小于 x 的元素的个数。利用这个信息，就可以直接把 x 放到它在最终输出数组中的正确位置上。这要求我们事先知道待排序数组的整数范围。 算法步骤分解 我们通过一个具体的例子来逐步讲解。假设输入数组为 [4, 2, 2, 8, 3, 3, 1] ，已知数组中最大的数是 8，即 k = 8。 步骤一：创建计数数组 首先，我们创建一个长度为 k+1 （即 8+1=9）的数组，称为计数数组（Count Array），并将其所有元素初始化为 0。这个数组的索引代表输入数组中元素的值，索引对应的值代表该元素出现的次数。 计数数组 count 初始状态： [0, 0, 0, 0, 0, 0, 0, 0, 0] 索引： 0, 1, 2, 3, 4, 5, 6, 7, 8 步骤二：统计每个元素的出现次数 我们遍历输入数组，对于遇到的每一个数字，就在计数数组相应索引的位置上加 1。 遍历过程： 遇到 4 -> count[4] 加 1，变为 1。 遇到 2 -> count[2] 加 1，变为 1。 遇到 2 -> count[2] 加 1，变为 2。 遇到 8 -> count[8] 加 1，变为 1。 遇到 3 -> count[3] 加 1，变为 1。 遇到 3 -> count[3] 加 1，变为 2。 遇到 1 -> count[1] 加 1，变为 1。 遍历完成后，计数数组变为： [0, 1, 2, 2, 1, 0, 0, 0, 1] 这表示：数字 0 出现 0 次，数字 1 出现 1 次，数字 2 出现 2 次，数字 3 出现 2 次，数字 4 出现 1 次，...，数字 8 出现 1 次。 步骤三：将计数数组转换为累积计数数组 这一步的目的是，让计数数组中的每个位置的值，等于输入数组中小于等于该索引值的元素的总个数。 我们遍历计数数组，将当前索引的值加上前一个索引的值。 转换过程（从索引 1 开始）： count[0] 保持 0。 count[1] = count[1] + count[0] = 1 + 0 = 1 （表示小于等于1的元素有1个） count[2] = count[2] + count[1] = 2 + 1 = 3 （表示小于等于2的元素有3个） count[3] = count[3] + count[2] = 2 + 3 = 5 （表示小于等于3的元素有5个） count[4] = count[4] + count[3] = 1 + 5 = 6 count[5] = count[5] + count[4] = 0 + 6 = 6 count[6] = 6 + 0 = 6 count[7] = 6 + 0 = 6 count[8] = 1 + 6 = 7 （表示小于等于8的元素有7个，即所有元素） 转换后的累积计数数组为： [0, 1, 3, 5, 6, 6, 6, 6, 7] 步骤四：根据累积计数数组，将元素放到输出数组的正确位置 我们创建一个和输入数组等长的输出数组 output 。 然后，我们 从后往前 遍历原始输入数组（这样做是为了保证排序的稳定性，即相等元素的相对顺序不变，虽然对于纯数字排序稳定性可能不重要，但这是一个好习惯）。 对于输入数组中的每一个元素 arr[i] ： 在累积计数数组中找到它的索引 index = arr[i] 。 查找该索引对应的值 count[index] ，这个值表示元素 arr[i] 在输出数组中的 最终位置（从1开始计数） 。因为数组索引从0开始，所以它在输出数组中的实际索引是 count[index] - 1 。 将 arr[i] 放入输出数组的 count[index] - 1 位置。 将累积计数数组中 count[index] 的值减 1（因为我们已经放置了一个值为 arr[i] 的元素，下一个相同的元素应该放在它前面的位置）。 遍历过程（输入数组 [4, 2, 2, 8, 3, 3, 1] ）： i=6, arr[6] = 1 : index = 1 , count[1] = 1 -> 位置是 1 - 1 = 0 。 将 1 放入 output[0] ， output 变为 [1, _, _, _, _, _, _] 。 count[1] 减 1，变为 0。计数数组变为 [0, 0, 3, 5, 6, 6, 6, 6, 7] 。 i=5, arr[5] = 3 : index = 3 , count[3] = 5 -> 位置是 5 - 1 = 4 。 将 3 放入 output[4] ， output 变为 [1, _, _, _, 3, _, _] 。 count[3] 减 1，变为 4。计数数组变为 [0, 0, 3, 4, 6, 6, 6, 6, 7] 。 i=4, arr[4] = 3 : index = 3 , count[3] = 4 -> 位置是 4 - 1 = 3 。 将 3 放入 output[3] ， output 变为 [1, _, _, 3, 3, _, _] 。 count[3] 减 1，变为 3。 i=3, arr[3] = 8 : index = 8 , count[8] = 7 -> 位置是 7 - 1 = 6 。 将 8 放入 output[6] ， output 变为 [1, _, _, 3, 3, _, 8] 。 count[8] 减 1，变为 6。 i=2, arr[2] = 2 : index = 2 , count[2] = 3 -> 位置是 3 - 1 = 2 。 将 2 放入 output[2] ， output 变为 [1, _, 2, 3, 3, _, 8] 。 count[2] 减 1，变为 2。 i=1, arr[1] = 2 : index = 2 , count[2] = 2 -> 位置是 2 - 1 = 1 。 将 2 放入 output[1] ， output 变为 [1, 2, 2, 3, 3, _, 8] 。 count[2] 减 1，变为 1。 i=0, arr[0] = 4 : index = 4 , count[4] = 6 -> 位置是 6 - 1 = 5 。 将 4 放入 output[5] ， output 变为 [1, 2, 2, 3, 3, 4, 8] 。 count[4] 减 1，变为 5。 步骤五：复制输出数组 此时， output 数组 [1, 2, 2, 3, 3, 4, 8] 就是排好序的数组。通常我们将 output 数组的内容复制回原数组 arr 。 复杂度分析 时间复杂度：O(n + k) 步骤二（统计频率）遍历 n 个元素。 步骤三（求累积和）和步骤四（放置元素）都遍历 k 个元素的计数数组。 所以总时间是 O(n + k)。 空间复杂度：O(n + k) 需要额外的输出数组 O(n)。 需要额外的计数数组 O(k)。 适用场景与局限性 优点 ：当整数范围 k 不大时，速度非常快，快于任何基于比较的排序算法（O(n log n)）。 局限性 ： 只能对整数进行排序。 需要事先知道待排序数据的范围（k 不能太大），如果 k 远大于 n（例如排序 [1, 1000000] ），则效率很低且浪费空间。