计数排序

问题

实现计数排序算法，对非负整数数组进行排序。

解答

基本实现

function countingSort(arr) {
  if (arr.length <= 1) return arr;

  // 找出最大值，确定计数数组的长度
  const max = Math.max(...arr);

  // 创建计数数组，初始化为 0
  const count = new Array(max + 1).fill(0);

  // 统计每个元素出现的次数
  for (const num of arr) {
    count[num]++;
  }

  // 根据计数数组重建排序结果
  const result = [];
  for (let i = 0; i <= max; i++) {
    while (count[i] > 0) {
      result.push(i);
      count[i]--;
    }
  }

  return result;
}

// 测试
console.log(countingSort([4, 2, 2, 8, 3, 3, 1])); // [1, 2, 2, 3, 3, 4, 8]
console.log(countingSort([5, 1, 3, 7, 2, 4, 6])); // [1, 2, 3, 4, 5, 6, 7]

稳定版本（保持相同元素的相对顺序）

function stableCountingSort(arr) {
  if (arr.length <= 1) return arr;

  const max = Math.max(...arr);
  const count = new Array(max + 1).fill(0);

  // 统计每个元素出现的次数
  for (const num of arr) {
    count[num]++;
  }

  // 计算前缀和，count[i] 表示 <= i 的元素个数
  for (let i = 1; i <= max; i++) {
    count[i] += count[i - 1];
  }

  // 从后向前遍历原数组，保证稳定性
  const result = new Array(arr.length);
  for (let i = arr.length - 1; i >= 0; i--) {
    const num = arr[i];
    // count[num] - 1 是该元素在结果数组中的位置
    result[count[num] - 1] = num;
    count[num]--;
  }

  return result;
}

// 测试
console.log(stableCountingSort([4, 2, 2, 8, 3, 3, 1])); // [1, 2, 2, 3, 3, 4, 8]

支持负数的版本

function countingSortWithNegative(arr) {
  if (arr.length <= 1) return arr;

  const min = Math.min(...arr);
  const max = Math.max(...arr);
  const range = max - min + 1;

  // 创建计数数组
  const count = new Array(range).fill(0);

  // 统计次数，使用偏移量处理负数
  for (const num of arr) {
    count[num - min]++;
  }

  // 重建结果
  const result = [];
  for (let i = 0; i < range; i++) {
    while (count[i] > 0) {
      result.push(i + min); // 加回偏移量
      count[i]--;
    }
  }

  return result;
}

// 测试
console.log(countingSortWithNegative([-3, 2, -1, 0, 4, -2, 1])); // [-3, -2, -1, 0, 1, 2, 4]

关键点

• 非比较排序，时间复杂度 O(n + k)，k 是数据范围
• 空间复杂度 O(k)，需要额外的计数数组
• 只适用于整数，且数据范围不宜过大
• 稳定版本需要计算前缀和，并从后向前遍历
• 处理负数需要使用偏移量将值映射到非负索引