【 已更新完 TypeScript 设计模式 专栏，感兴趣可以关注一下，一起学习交流🔥🔥🔥 】

1. 计数排序简介

1.1 计数排序定义

计数排序是一种非比较性的整数排序算法。它的核心思想是"统计数字出现次数，然后按顺序重建数组"。假如你是一位邮局工作人员，需要整理一大堆混乱的邮件，你采用这样的策略：首先统计每个邮政编码的邮件有多少封，按照邮政编码顺序，将邮件重新排列在分拣架上，这就是计数排序的基本思想。

用TypeScript代码表示一个简单的计数排序：

typescript">function countingSort(arr: number[]): number[] {if (arr.length <= 1) return arr;const max = Math.max(...arr);const counts = new Array(max + 1).fill(0);for (const num of arr) {counts[num]++;}const sortedArray: number[] = [];for (let i = 0; i <= max; i++) {while (counts[i] > 0) {sortedArray.push(i);counts[i]--;}}return sortedArray;
}

1.2 计数排序特点

1. 线性时间复杂度：计数排序的时间复杂度为O(n+k)，其中n是数组长度，k是数组中的最大值
2. 非比较排序：计数排序不通过比较元素来排序，通过统计元素出现的次数
3. 稳定性：计数排序是稳定的排序算法
4. 适用范围：适用于已知范围的整数排序，特别是当范围不是很大的时候

2. 计数排序步骤过程拆解

2.1 找出数组中的最大值

typescript">const max = Math.max(...arr);

像邮局工作人员找出所有邮件中邮政编码最大的那一个，这个最大邮政编码将决定我们需要准备多少个"计数格子"。

2.2 创建计数数组

typescript">const counts = new Array(max + 1).fill(0);

这个步骤就像邮局工作人员准备了一排从0到最大邮政编码的小格子，每个格子里放一个计数器，初始值都是0。

2.3 统计每个数字出现的次数

typescript">for (const num of arr) {counts[num]++;
}

这个过程就像邮局工作人员收到一封邮件，看一眼邮政编码，然后在对应的格子里的计数器加1。

2.4 重建排序后的数组

typescript">const sortedArray: number[] = [];
for (let i = 0; i <= max; i++) {while (counts[i] > 0) {sortedArray.push(i);counts[i]--;}
}

这个步骤就像邮局工作人员从邮政编码0开始，查看每个格子里的计数器，如果不为0，就放入相应数量的该邮政编码的邮件，接着移动到下一个格子，直到所有的邮件都分类完毕。

3. 计数排序的优化

3.1 处理负数

typescript">function countingSortWithNegatives(arr: number[]): number[] {if (arr.length <= 1) return arr;const min = Math.min(...arr);const max = Math.max(...arr);const range = max - min + 1;const counts = new Array(range).fill(0);for (const num of arr) {counts[num - min]++;}const sortedArray: number[] = [];for (let i = 0; i < range; i++) {while (counts[i] > 0) {sortedArray.push(i + min);counts[i]--;}}return sortedArray;
}

这个优化版本就像邮局工作人员遇到了一些特殊的负数编号的邮件，他不再从0开始计数，而是从最小的编号开始，这样就可以处理所有的邮件了，无论编号是正数还是负数。

3.2 对象数组排序

typescript">interface Book {id: number;title: string;
}function countingSortBooks(books: Book[]): Book[] {if (books.length <= 1) return books;const max = Math.max(...books.map(book => book.id));const counts: Book[][] = new Array(max + 1).fill(null).map(() => []);for (const book of books) {counts[book.id].push(book);}const sortedBooks: Book[] = [];for (const bookList of counts) {sortedBooks.push(...bookList);}return sortedBooks;
}

这个优化版本就像邮局工作人员不仅要整理邮件的邮政编码，还要保持每封邮件的其他信息（如邮件内容）。他在每个计数格子里不再放简单的数字，而是放一个可以容纳多封邮件信息的"小篮子"。

案例代码和动态图

typescript">const numbers = [4, 2, 2, 8, 3, 3, 1];
const sortedNumbers = countingSort(numbers);
console.log(sortedNumbers); // [1, 2, 2, 3, 3, 4, 8]const books: Book[] = [{ id: 3, title: "TypeScript基础" },{ id: 1, title: "JavaScript高级程序设计" },{ id: 3, title: "深入理解TypeScript" },{ id: 2, title: "你不知道的JavaScript" }
];
const sortedBooks = countingSortBooks(books);
console.log(sortedBooks);
// [
//   { id: 1, title: "JavaScript高级程序设计" },
//   { id: 2, title: "你不知道的JavaScript" },
//   { id: 3, title: "TypeScript基础" },
//   { id: 3, title: "深入理解TypeScript" }
// ]

4. 计数排序的优点

1. 时间复杂度低：在特定情况下，计数排序的时间复杂度可以达到O(n)，这比基于比较的排序算法更快
2. 稳定性：计数排序是稳定的排序算法，这在某些应用场景中非常重要
3. 适合大数据量、取值范围集中的数据排序：当数据量很大但取值范围相对集中时，计数排序的优势尤为明显

5. 计数排序的缺点

1. 空间复杂度高：计数排序需要额外的存储空间来记录每个元素的出现次数
2. 适用范围有限：计数排序只适用于整数或可以转化为整数的数据
3. 当数据范围很大时效率降低：如果数据范围远大于数据量，计数排序的空间复杂度和时间复杂度都会急剧增加

总结

计数排序告诉我们，面对一堆看似杂乱无章的数据，有时候直接比较和交换并不是最有效的方法。通过统计每个数字出现的次数，我们可以直接还原出有序的序列。这种"以静制动"的思想不仅在排序中有用，在我们日常解决问题时也常常能派上用场。

喜欢的话就点个赞 ❤️，关注一下吧，有问题也欢迎讨论指教。感谢大家!!!

下期预告: TypeScript 算法手册 - 基数排序