排序系列

前言

大家好，我是老马。

以前从工程的角度，已经梳理过一次排序算法。

这里从力扣算法的角度，重新梳理一遍。

核心内容包含：

1）常见排序算法介绍

2）背后的核心思想

3）leetcode 经典题目练习+讲解

4）应用场景、优缺点等对比总结

5）工程 sdk 包，这个已经完成。

6) 可视化

下面是常见排序算法的完整对比表，包括：时间复杂度、空间复杂度、是否稳定、优缺点等信息，方便系统地掌握。

算法	时间复杂度 (平均/最坏)	空间复杂度	稳定性	优点	缺点
冒泡排序 Bubble Sort	O(n²) / O(n²)	O(1)	✅ 稳定	实现简单，适合教学	效率极低，适合数据很小或几乎有序
选择排序 Selection Sort	O(n²) / O(n²)	O(1)	❌ 不稳定	交换次数少，结构清晰	比冒泡还慢，不能利用已有序性
插入排序 Insertion Sort	O(n²) / O(n²)	O(1)	✅ 稳定	适合小规模、部分有序数据	大数据量时效率低

算法	时间复杂度 (平均/最坏)	空间复杂度	稳定性	优点	缺点
归并排序 Merge Sort	O(n log n) / O(n log n)	O(n)	✅ 稳定	稳定，时间稳定，适合链表等结构	空间消耗大，递归实现复杂
快速排序 Quick Sort	O(n log n) / O(n²)	O(log n)（递归栈）	❌ 不稳定	平均快，原地排序，实用性强	最坏情况退化为 O(n²)，不稳定
希尔排序 Shell Sort	约 O(n¹.³) / O(n²)	O(1)	❌ 不稳定	改进插入排序，速度提升大	增量序列选择影响性能，难分析
堆排序 Heap Sort	O(n log n) / O(n log n)	O(1)	❌ 不稳定	不使用递归，不需要额外内存	实现略复杂，不稳定

算法	时间复杂度 (平均/最坏)	空间复杂度	稳定性	优点	缺点
计数排序 Counting Sort	O(n + k) / O(n + k)	O(k)	✅ 稳定	非比较排序，适合范围小的整数	数据范围大时空间消耗严重
桶排序 Bucket Sort	O(n + k) / O(n²)	O(n + k)	✅ 稳定	适合小数和均匀分布	依赖数据分布，桶内排序开销大
基数排序 Radix Sort	O(n·k) / O(n·k)	O(n + k)	✅ 稳定	适合定长整数或字符串，效率高	需要额外空间，非比较型，不通用

注：k 表示值域或位数（如基数或最大整数范围）

下面是每种常见排序算法的核心思想简要总结，帮你快速理解“它到底在干什么”。

算法	核心思想
冒泡排序 Bubble Sort	反复比较相邻元素，大的往后交换，让最大元素“像气泡一样”冒到最后。
选择排序 Selection Sort	每次从未排序区域中选择最小值，放到已排序区的末尾。
插入排序 Insertion Sort	类似整理扑克牌，将当前元素插入到前面已排好序的部分中合适的位置。

算法	核心思想
归并排序 Merge Sort	典型分治法：先分成左右两半，分别排序，再把两个有序数组合并。
快速排序 Quick Sort	也是分治法：选一个“基准值”，把比它小的放左边，大的放右边，然后递归排序两边。
希尔排序 Shell Sort	对插入排序的改进：先分组进行粗排序，然后逐步缩小间隔，最后整体插入排序。
堆排序 Heap Sort	利用堆这种数据结构，不断取出堆顶最大/最小值，然后重新调整成堆。

算法	核心思想
计数排序 Counting Sort	建一个计数数组记录每个数的出现次数，然后按顺序还原排序结果。
桶排序 Bucket Sort	把数据按范围分到多个桶里，每个桶内部排序后合并。
基数排序 Radix Sort	按数字的每一位从低到高进行多轮排序，常用计数排序做子步骤。