计数排序（Counting Sort）的进阶应用：对包含负数的整数数组进行排序的优化与稳定性证明（二次讲解）
字数 2235 2025-12-11 13:45:24

计数排序（Counting Sort）的进阶应用：对包含负数的整数数组进行排序的优化与稳定性证明（二次讲解）

题目描述

给定一个整数数组 arr，其中可能包含负数、零和正数，要求使用计数排序（Counting Sort） 对该数组进行升序排序。计数排序通常用于非负整数，但我们需要将其扩展以支持负数。同时，需要保证排序的稳定性（即相等元素的原始相对顺序保持不变），并分析时间复杂度和空间复杂度。

解题过程

步骤1：理解计数排序的基本原理

计数排序是一种非比较排序，适用于整数范围已知且较小的情况。其核心思想是：

  1. 统计每个元素出现的次数。
  2. 计算每个元素在排序后数组中的位置。
  3. 将元素按统计结果放入正确位置。

对于非负整数数组，假设元素范围在 [0, k]，算法步骤如下：

  • 创建计数数组 count，长度为 k+1，初始化全为0。
  • 遍历原数组，统计每个元素出现次数，存入 count。
  • 对 count 做前缀和，使得 count[i] 表示小于等于 i 的元素个数。
  • 从后向前遍历原数组，根据 count 确定元素位置，并更新 count。

但原版计数排序无法直接处理负数，因为数组索引不能为负。

步骤2：扩展计数排序以支持负数

关键思路：将负数映射到非负索引。

  1. 找到数组中的最小值 min 和最大值 max。
  2. 计算偏移量 offset = -min（如果 min 为负数，则 offset 为正数）。
  3. 创建计数数组 count，长度为 max - min + 1。
  4. 遍历原数组，对每个元素 x，将其映射到索引 x + offset，并增加计数。
  5. 对 count 做前缀和。
  6. 从后向前遍历原数组，利用 count 和 offset 反向映射，将元素放入结果数组的正确位置。

示例：
数组 arr = [4, -2, 1, -2, 3, -1]

  • min = -2, max = 4
  • offset = 2
  • 计数数组长度 = 4 - (-2) + 1 = 7，索引范围 [0, 6]，对应原值 [-2, -1, 0, 1, 2, 3, 4]。

映射关系：
原值 -2 → 索引 0
原值 -1 → 索引 1
...
原值 4 → 索引 6

步骤3：保证稳定性

计数排序的稳定性依赖于从后向前遍历原数组放置元素。

  • 前缀和数组 count[i] 表示小于等于原值 i 的元素个数（注意这里 i 是原值，不是索引）。
  • 从后向前遍历原数组时，遇到元素 x，其应放置的位置是 count[x + offset] - 1（因为索引从0开始）。
  • 放置后，将 count[x + offset] 减1，确保相同元素中靠前的那个会被放在靠后的位置（因为遍历顺序是从后向前，但相同元素的相对顺序被反向保持了）。

稳定性证明：
设原数组中有两个相等元素 a[i] 和 a[j]（i < j）。在从后向前遍历时，先遇到 a[j]，将其放在位置 pos_j = count[val] - 1，然后 count[val]--。接着遇到 a[i]，此时 count[val] 已减少，因此 a[i] 被放在 pos_i = count[val] - 1，且 pos_i < pos_j。在结果数组中，a[i] 在 a[j] 之前，保持了原始顺序（i < j），因此稳定。

步骤4：算法实现细节

  1. 遍历数组，找出 min 和 max。
  2. 创建计数数组 count，长度 = max - min + 1。
  3. 第一次遍历原数组，统计频率：count[arr[i] - min]++。
  4. 对 count 做前缀和：count[i] += count[i-1]（从 i=1 开始）。
  5. 创建结果数组 output，长度与原数组相同。
  6. 从后向前遍历原数组：
    • 计算索引 idx = arr[i] - min。
    • 输出位置 pos = count[idx] - 1。
    • output[pos] = arr[i]。
    • count[idx]--。
  7. 将 output 复制回原数组（或直接返回）。

步骤5：复杂度分析

  • 时间复杂度：O(n + k)，其中 n 是数组长度，k = max - min + 1 是数值范围长度。
  • 空间复杂度：O(n + k)，用于计数数组和输出数组。

当 k 远小于 n 时，计数排序效率很高；若 k 很大（例如范围过大），则空间开销大，可能不适用。

步骤6：边界情况处理

  • 数组为空或长度为1：直接返回。
  • 所有元素相同：算法正常工作。
  • 最小值或最大值为负数：偏移量 offset 自动处理。
  • 包含极大或极小数：若范围过大，应考虑其他排序算法。

步骤7：总结与扩展

本方法通过偏移映射将负数转换为非负索引，使计数排序支持全整数范围。稳定性通过反向放置和计数递减保证。该算法在数值范围有限的场景下非常高效，且由于是非比较排序，其时间复杂度突破了 Ω(n log n) 的下界（仅适用于比较排序）。

进一步优化：如果内存紧张，可尝试用更紧凑的数据结构存储计数，或对超大范围采用分段计数排序。

计数排序（Counting Sort）的进阶应用：对包含负数的整数数组进行排序的优化与稳定性证明（二次讲解） 题目描述 给定一个整数数组 arr ，其中可能包含 负数、零和正数 ，要求使用 计数排序（Counting Sort） 对该数组进行升序排序。计数排序通常用于非负整数，但我们需要将其扩展以支持负数。同时，需要 保证排序的稳定性 （即相等元素的原始相对顺序保持不变），并分析时间复杂度和空间复杂度。 解题过程 步骤1：理解计数排序的基本原理 计数排序是一种 非比较排序 ，适用于 整数范围已知且较小 的情况。其核心思想是： 统计每个元素出现的次数。 计算每个元素在排序后数组中的位置。 将元素按统计结果放入正确位置。 对于非负整数数组，假设元素范围在 [0, k] ，算法步骤如下： 创建计数数组 count ，长度为 k+1 ，初始化全为0。 遍历原数组，统计每个元素出现次数，存入 count 。 对 count 做前缀和，使得 count[i] 表示 小于等于 i 的元素个数 。 从后向前遍历原数组，根据 count 确定元素位置，并更新 count 。 但原版计数排序 无法直接处理负数 ，因为数组索引不能为负。 步骤2：扩展计数排序以支持负数 关键思路： 将负数映射到非负索引 。 找到数组中的最小值 min 和最大值 max 。 计算偏移量 offset = -min （如果 min 为负数，则 offset 为正数）。 创建计数数组 count ，长度为 max - min + 1 。 遍历原数组，对每个元素 x ，将其映射到索引 x + offset ，并增加计数。 对 count 做前缀和。 从后向前遍历原数组，利用 count 和 offset 反向映射，将元素放入结果数组的正确位置。 示例 ： 数组 arr = [4, -2, 1, -2, 3, -1] min = -2 , max = 4 offset = 2 计数数组长度 = 4 - (-2) + 1 = 7 ，索引范围 [0, 6] ，对应原值 [-2, -1, 0, 1, 2, 3, 4] 。 映射关系： 原值 -2 → 索引 0 原值 -1 → 索引 1 ... 原值 4 → 索引 6 步骤3：保证稳定性 计数排序的稳定性依赖于 从后向前遍历原数组 放置元素。 前缀和数组 count[i] 表示 小于等于原值 i 的元素个数 （注意这里 i 是原值，不是索引）。 从后向前遍历原数组时，遇到元素 x ，其应放置的位置是 count[x + offset] - 1 （因为索引从0开始）。 放置后，将 count[x + offset] 减1，确保相同元素中靠前的那个会被放在靠后的位置（因为遍历顺序是从后向前，但相同元素的相对顺序被反向保持了）。 稳定性证明 ： 设原数组中有两个相等元素 a[i] 和 a[j] （ i < j ）。在从后向前遍历时，先遇到 a[j] ，将其放在位置 pos_j = count[val] - 1 ，然后 count[val]-- 。接着遇到 a[i] ，此时 count[val] 已减少，因此 a[i] 被放在 pos_i = count[val] - 1 ，且 pos_i < pos_j 。在结果数组中， a[i] 在 a[j] 之前，保持了原始顺序（ i < j ），因此稳定。 步骤4：算法实现细节 遍历数组，找出 min 和 max 。 创建计数数组 count ，长度 = max - min + 1 。 第一次遍历原数组，统计频率： count[arr[i] - min]++ 。 对 count 做前缀和： count[i] += count[i-1] （从 i=1 开始）。 创建结果数组 output ，长度与原数组相同。 从后向前遍历原数组： 计算索引 idx = arr[i] - min 。 输出位置 pos = count[idx] - 1 。 output[pos] = arr[i] 。 count[idx]-- 。 将 output 复制回原数组（或直接返回）。 步骤5：复杂度分析 时间复杂度：O(n + k)，其中 n 是数组长度， k = max - min + 1 是数值范围长度。 空间复杂度：O(n + k)，用于计数数组和输出数组。 当 k 远小于 n 时，计数排序效率很高；若 k 很大（例如范围过大），则空间开销大，可能不适用。 步骤6：边界情况处理 数组为空或长度为1：直接返回。 所有元素相同：算法正常工作。 最小值或最大值为负数：偏移量 offset 自动处理。 包含极大或极小数：若范围过大，应考虑其他排序算法。 步骤7：总结与扩展 本方法通过 偏移映射 将负数转换为非负索引，使计数排序支持全整数范围。稳定性通过 反向放置和计数递减 保证。该算法在 数值范围有限 的场景下非常高效，且由于是非比较排序，其时间复杂度突破了 Ω(n log n) 的下界（仅适用于比较排序）。 进一步优化 ：如果内存紧张，可尝试用更紧凑的数据结构存储计数，或对超大范围采用分段计数排序。