排序算法通关攻略：非比较排序三兄弟（计数/桶/基数排序）

📝 写在前面

上一期我们学了六种比较排序，它们都是通过元素之间的比较来决定顺序。今天来认识三位"不走寻常路"的排序算法——计数排序、桶排序、基数排序。它们的共同特点是：不通过比较，而是利用数据本身的特性来排序。

为什么需要它们？

• 比较排序的下界是 O(n log n) 

• 非比较排序在某些情况下可以达到 O(n) 的线性时间复杂度！

• 但代价是：对数据有特殊要求，且需要额外空间

阅读指南：每个算法包含

• 生活比喻：一句话记住核心思想

• 算法可视化：算法流程图

• 代码实现：带详细注释

• LeetCode实战：用真题巩固理解

一、非比较排序全家福

💡 注：k 是数据范围（最大值-最小值），d 是位数

二、计数排序（Counting Sort）—— 点名神器

🎯 一句话记住

就像老师点名：统计每个分数有多少人，然后按分数把人排好。

🤔 核心思想

不比较元素大小，而是统计每个元素出现的次数，然后根据次数直接把元素放到正确位置 。

举个栗子：对 [2, 5, 3, 0, 2, 3, 0, 3] 排序

💻 代码实现

/**
* 计数排序
* @param {number[]} arr 待排序数组（非负整数）
* @returns {number[]} 排序后数组
*/
function countingSort(arr) {
if (arr.length <= 1) return arr;

// 1. 找到最大值和最小值，确定范围
let max = Math.max(…arr);
let min = Math.min(…arr);
const range = max – min + 1;

// 2. 创建计数数组并统计每个元素出现次数
const count = new Array(range).fill(0);
for (let i = 0; i < arr.length; i++) {
count[arr[i] – min]++; // 偏移量索引
}

// 3. 前缀和：count[i]现在表示小于等于i+min的元素个数
for (let i = 1; i < range; i++) {
count[i] += count[i – 1];
}

// 4. 从后往前遍历原数组，放入输出数组（保证稳定性）
const output = new Array(arr.length);
for (let i = arr.length – 1; i >= 0; i–) {
const val = arr[i];
const idx = val – min;
const pos = count[idx] – 1;
output[pos] = val;
count[idx]–; // 处理相同元素
}

// 5. 复制回原数组
for (let i = 0; i < arr.length; i++) {
arr[i] = output[i];
}
return arr;
}

// 测试
console.log(countingSort([2, 5, 3, 0, 2, 3, 0, 3]));
// [0, 0, 2, 2, 3, 3, 3, 5]

🏆 LeetCode实战：颜色分类（计数排序版）

题目：LeetCode 75. 颜色分类 

题目描述：给定一个包含红色、白色和蓝色，共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。

思路分析： 这道题是计数排序的完美应用场景 ：

第一，只有3种值（0、1、2），范围极小

第二，可以统计每种颜色出现次数，然后直接覆盖原数组

解题代码：

/**
* @param {number[]} nums
* @return {void} 原地修改
*/
var sortColors = function(nums) {
// 1. 统计0、1、2出现的次数
const count = [0, 0, 0];
for (let i = 0; i < nums.length; i++) {
count[nums[i]]++;
}

// 2. 按照次数重新填充数组
let index = 0;
for (let color = 0; color <= 2; color++) {
for (let j = 0; j < count[color]; j++) {
nums[index++] = color;
}
}
};

// 更简洁的写法（两次遍历）
var sortColors = function(nums) {
const count = [0, 0, 0];
for (let num of nums) count[num]++;
let i = 0;
for (let color = 0; color < 3; color++) {
while (count[color]– > 0) nums[i++] = color;
}
};

时间复杂度：O(n) 空间复杂度：O(1)（因为k=3是常数）

进阶思考：这道题还有更优的一次遍历 + 双指针解法。

三、桶排序（Bucket Sort）—— 分桶管理

🎯 一句话记住

就像垃圾分类：先把垃圾按类别扔进不同桶，再对每个桶单独整理。

🤔 核心思想

将元素分到有限数量的桶里，每个桶再分别排序（可以用其他排序或递归桶排序），最后按顺序合并 。

适用场景：数据均匀分布时效率最高 

举个栗子：对 [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68] 排序

📊 算法流程图

💻 代码实现

/**
* 桶排序（处理[0,1)范围内的浮点数）
* @param {number[]} arr 待排序数组（元素范围[0,1)）
* @param {number} bucketSize 桶的大小（每个桶能放多少元素）
* @returns {number[]} 排序后数组
*/
function bucketSort(arr, bucketSize = 5) {
if (arr.length <= 1) return arr;

// 1. 找到最小值和最大值
const min = Math.min(…arr);
const max = Math.max(…arr);

// 2. 计算桶的数量
const bucketCount = Math.floor((max – min) / bucketSize) + 1;
const buckets = new Array(bucketCount).fill().map(() => []);

// 3. 将元素分配到各个桶中
for (let i = 0; i < arr.length; i++) {
const bucketIndex = Math.floor((arr[i] – min) / bucketSize);
buckets[bucketIndex].push(arr[i]);
}

// 4. 对每个桶进行排序（这里用插入排序）
const result = [];
for (let i = 0; i < buckets.length; i++) {
if (buckets[i].length > 0) {
// 对桶内元素进行插入排序
insertionSort(buckets[i]);
// 合并结果
result.push(…buckets[i]);
}
}

return result;
}

/**
* 插入排序（用于桶内排序）
*/
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
const key = arr[i];
let j = i – 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j–;
}
arr[j + 1] = key;
}
return arr;
}

// 测试
console.log(bucketSort([0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]));
// [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]

🏆 LeetCode实战：最大间距（桶排序优化）

题目：LeetCode 164. 最大间距 

题目描述：给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0。要求：线性时间复杂度。

思路分析： 这道题要求 O(n) 时间，不能用普通排序。巧用桶排序 ：

解题代码：

/**
* @param {number[]} nums
* @return {number}
*/
var maximumGap = function(nums) {
if (nums.length < 2) return 0;

const n = nums.length;
let min = Math.min(…nums);
let max = Math.max(…nums);

// 如果所有元素相等，间距为0
if (max === min) return 0;

// 1. 计算桶的大小（确保桶的数量为n-1）
const bucketSize = Math.max(1, Math.floor((max – min) / (n – 1)));
const bucketCount = Math.floor((max – min) / bucketSize) + 1;

// 2. 初始化桶，每个桶记录最大值和最小值
const buckets = new Array(bucketCount).fill().map(() => ({
min: Infinity,
max: -Infinity,
used: false
}));

// 3. 将元素放入桶中
for (let i = 0; i < n; i++) {
const num = nums[i];
const idx = Math.floor((num – min) / bucketSize);
buckets[idx].min = Math.min(buckets[idx].min, num);
buckets[idx].max = Math.max(buckets[idx].max, num);
buckets[idx].used = true;
}

// 4. 计算桶间最大间距
let maxGap = 0;
let prevMax = min;

for (let i = 0; i < bucketCount; i++) {
if (!buckets[i].used) continue;
// 当前桶的最小值减去上一个桶的最大值
maxGap = Math.max(maxGap, buckets[i].min – prevMax);
prevMax = buckets[i].max;
}

return maxGap;
};

时间复杂度：O(n) 空间复杂度：O(n)

四、基数排序（Radix Sort）—— 按位分配

🎯 一句话记住

就像整理扑克牌：先按个位数分堆，再按十位数分堆，最后按百位数分堆。

🤔 核心思想

将整数按位数切割，从低位到高位（LSD）或高位到低位（MSD）依次分配 。

两种方式 ：

• LSD（最低位优先）：从个位开始，逐位处理，需要稳定排序

• MSD（最高位优先）：从高位开始，递归处理，适合字符串

举个栗子：对 [170, 45, 75, 90, 2, 802, 24, 66] 进行LSD基数排序

💻 代码实现

/**
* 基数排序（LSD版）
* @param {number[]} arr 待排序数组（非负整数）
* @returns {number[]} 排序后数组
*/
function radixSort(arr) {
if (arr.length <= 1) return arr;

// 1. 找到最大值，确定最大位数
const max = Math.max(…arr);

// 2. 从个位开始，逐位处理
for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
countingSortByDigit(arr, exp);
}

return arr;
}

/**
* 根据某一位进行计数排序（稳定排序）
* @param {number[]} arr
* @param {number} exp 位数（1=个位，10=十位，100=百位…）
*/
function countingSortByDigit(arr, exp) {
const n = arr.length;
const output = new Array(n);
const count = new Array(10).fill(0); // 只有0-9十个数字

// 1. 统计当前位每个数字出现的次数
for (let i = 0; i < n; i++) {
const digit = Math.floor(arr[i] / exp) % 10;
count[digit]++;
}

// 2. 前缀和
for (let i = 1; i < 10; i++) {
count[i] += count[i – 1];
}

// 3. 从后往前放置元素（保证稳定性）
for (let i = n – 1; i >= 0; i–) {
const digit = Math.floor(arr[i] / exp) % 10;
const pos = count[digit] – 1;
output[pos] = arr[i];
count[digit]–;
}

// 4. 复制回原数组
for (let i = 0; i < n; i++) {
arr[i] = output[i];
}
}

// 测试
console.log(radixSort([170, 45, 75, 90, 2, 802, 24, 66]));
// [2, 24, 45, 66, 75, 90, 170, 802]

🏆 LeetCode实战：最大间距（基数排序版）

题目：LeetCode 164. 最大间距 

思路分析： 除了桶排序，这道题也可以用基数排序来做 ：

解题代码：

/**
* @param {number[]} nums
* @return {number}
*/
var maximumGap = function(nums) {
if (nums.length < 2) return 0;

// 1. 基数排序
radixSort(nums);

// 2. 找最大间距
let maxGap = 0;
for (let i = 1; i < nums.length; i++) {
maxGap = Math.max(maxGap, nums[i] – nums[i – 1]);
}

return maxGap;
};

// 复用上面的 radixSort 函数

时间复杂度：O(d × n)，d是最大位数 空间复杂度：O(n)

五、三兄弟对比总结

📌 什么时候用哪个？

• 数据范围小且是整数 → 计数排序（最简单）

• 数据均匀分布 → 桶排序（最灵活）

• 整数且位数不多 → 基数排序（最稳定）

• 数据量极大，内存有限 → 外部排序（桶排序的扩展）

🎯 下期预告

下一期我们将进入查找算法的世界：二分查找、二叉搜索树、哈希表——从有序数据中快速找到目标！

如果你觉得这篇文章对你有帮助，欢迎点赞、收藏、转发！有问题欢迎在评论区讨论～