排序算法

八大排序·一口清

速背口诀

“小插希，选交换；堆保坏，泡教学；快当家，归稳定，基数定长飞。”

一、直接插入排序（Insertion Sort）

核心操作

1. 逐个插入：将数组分为已排序区（初始为第1个元素）和未排序区；
2. 找位置：从末排序区取第一个元素，在已排序区中从后往前遍历，找到它的插入位置（比它大的元素后移）；
3. 插入元素：将当前元素插入到目标位置，已排序区长度+1，重复直到未排序区为空。

复杂度

适合场景（含例子）

• 小规模数据排序：当数据量n≤100时，O(n²)的复杂度可接受，且代码简单、常数项小（实际执行快）。
  例：对班级内30名学生的学号（无序）排序，直接插入排序比复杂的O(n log n)算法更高效。
• 接近有序的数据排序：若数据已部分有序（如大部分元素位置正确，仅少数乱序），最好情况可达到O(n)。
  例：对“每日新增用户列表”排序（新增用户按时间插入，列表整体接近有序），插入排序无需频繁移动元素。
• 嵌入式/内存受限场景：仅需O(1)额外空间，适合内存极小的设备（如单片机、传感器）。
  例：传感器采集的10个温度数据，在设备端用插入排序整理后上传，无需额外内存。

致命缺点

• “逆序即崩”：只要数据整体逆序，比较+移动次数双双飙到 n²/2，常数还大，稍大数组直接卡死；嵌入式场景下 n>1000 就别考虑。

二、希尔排序（Shell Sort）

核心操作

1. 分组插入：按**增量（Gap）**将数组分为多个子数组（如Gap=5时，子数组为[arr[0],arr[5],arr[10]…]）；
2. 子数组排序：对每个子数组用“直接插入排序”排序；
3. 缩小增量：逐步减小Gap（如从n/2→n/4→…→1），重复分组和排序；
4. 最终排序：当Gap=1时，数组整体变为一个子数组，用插入排序完成最终排序。

复杂度

适合场景（含例子）

• 中等规模数据排序：效率介于插入排序（O(n²)）和快排（O(n log n)）之间，代码比快排简单，适合n=1000~10000的场景。
  例：对公司5000名员工的工龄（无序）排序，希尔排序比插入排序快，且无需快排的递归栈空间。
• 不要求稳定性的场景：因分组排序会打乱相等元素的相对位置（如子数组[3,1,3]，Gap=2时排序后可能变为[1,3,3]，原两个3的位置交换），适合对稳定性无要求的场景。
  例：对商品的销量（仅需数值有序，无需区分相同销量的商品顺序）排序。
• 内存受限设备：同插入排序，仅需O(1)空间，适合嵌入式设备处理中等规模数据。

致命缺点

• 增量玄学：不同机器、实现、数据性能无法预测，性能与增量序列强相关，无统一紧确界；实际工程中很难预估运行时间，抖动大，critical-path 场景基本不敢用。

三、简单选择排序（Selection Sort）

核心操作

1. 找最小值：将数组分为“已排序区”（初始为空）和“未排序区”（初始为整个数组），遍历未排序区找到最小值；
2. 交换位置：将最小值与未排序区的第一个元素交换，最小值加入已排序区；
3. 重复执行：缩小未排序区范围（去掉第一个元素），重复“找最小值→交换”，直到未排序区为空。

复杂度

适合场景（含例子）

• 数据量极小且交换成本低的场景：虽时间复杂度为O(n²)，但找最小值的比较次数固定（n(n-1)/2），交换次数仅n-1次（远少于冒泡排序），适合交换成本高的场景。
  例：对存储在机械硬盘上的10个大文件（每个1GB）按大小排序，交换文件位置的成本高，选择排序仅需10次交换，比冒泡排序（最多45次交换）更优。
• 硬件资源极有限的场景：代码逻辑最简单（仅需嵌套循环+交换），适合无操作系统的裸机环境（如早期计算器、简易控制器）。
  例：计算器对输入的5个数字排序，用选择排序可简化代码实现。
• 不要求稳定性的场景：交换最小值时会打乱相等元素顺序（如数组[2,1,2]，第一次交换后变为[1,2,2]，原第一个2和第二个2的位置交换），适合对稳定性无要求的场景。

致命缺点

• 比较次数铁打不动；无论数据多有序，n(n-1)/2 次比较一次少不了，CPU cache 友好也救不了，规模一过百就废。

四、堆排序（Heap Sort）

核心操作

1. 构建大顶堆：将无序数组调整为“大顶堆”（父节点值≥子节点值），堆顶为数组最大值；
2. 堆顶交换：将堆顶（最大值）与堆的最后一个元素交换，最大值加入“已排序区”（堆大小减1）；
3. 堆调整（Heapify）：交换后堆结构被破坏，从堆顶开始向下调整，恢复大顶堆结构；
4. 重复执行：重复“堆顶交换→堆调整”，直到堆大小为1，数组完全有序。

复杂度

适合场景（含例子）

• 需要“最坏情况O(n log n)”且空间敏感的场景：快排最坏情况为O(n²)，堆排无论数据分布如何，时间复杂度均为O(n log n)，且无需额外空间。
  例：对金融交易数据（要求排序结果绝对可靠，不能因数据逆序导致排序超时）排序，堆排比快排更安全。
• Top-K问题（找前K个最大/最小值）：无需全量排序，只需构建大小为K的小顶堆/大顶堆，时间复杂度O(n log K)，效率远高于全量排序。
  例：从100万条用户评论中找点赞数前10的评论，构建大小为10的小顶堆，遍历一次数据即可完成，无需排序100万条数据。
• 嵌入式/实时系统：无递归（避免栈溢出）、原地排序，适合对实时性要求高的系统（如工业控制中的数据优先级排序）。

致命缺点

• “缓存杀手”：堆化过程跳跃式访问数组，cache miss 率远高于快排；同规模实测慢 2~3 倍，除非求稳或 Top-K，否则别当主力

五、冒泡排序（Bubble Sort）

核心操作

1. 相邻比较交换：从数组起始位置开始，依次比较相邻两个元素（arr[i]和arr[i+1]），若arr[i]＞arr[i+1]，则交换两者位置（大元素“冒泡”到右侧）；
2. 一轮冒泡：完成一轮遍历后，最大的元素会“冒泡”到数组末尾（加入已排序区）；
3. 优化终止：若某一轮遍历中未发生任何交换，说明数组已有序，直接终止排序（避免无效循环）；
4. 重复执行：缩小未排序区范围，重复“相邻比较交换”，直到未排序区为空。

复杂度

适合场景（含例子）

• 教学/演示场景：逻辑最简单（仅相邻比较交换），是理解“排序本质”的入门算法，适合教学演示排序过程。
  例：在编程入门课程中，用冒泡排序演示“如何通过重复操作让数据有序”，帮助新手理解算法思想。
• 数据量极小且接近有序的场景：若数据已完全有序，优化后的冒泡排序仅需O(n)时间，且代码简单。
  例：对“已按日期排序的日志列表”（仅新增1条日志插在中间）排序，冒泡排序一轮遍历即可完成。
• 无需效率的简单场景：如对个人通讯录的3个联系人按姓名排序，冒泡排序的代码量最少，开发成本最低。

致命缺点

• “交换次数比插入还多”；每次交换 3 次赋值，已有序场景也不如插入排序快；除了写板书，任何性能敏感代码都不考虑。

六、快速排序（Quick Sort）

核心操作

1. 选基准（Pivot）：从数组中选择一个元素作为基准（常用“三数取中法”：取首、尾、中三个元素的中位数，避免最坏情况）；
2. 分区（Partition）：遍历数组，将小于基准的元素移到左侧，大于基准的元素移到右侧，基准最终落在“正确位置”（左侧均≤基准，右侧均≥基准）；
3. 递归排序：对基准左侧和右侧的子数组，重复“选基准→分区”操作，直到子数组长度为1（天然有序）。

复杂度

适合场景（含例子）

• 内存中的中大规模随机数据排序：平均时间复杂度O(n log n)，且缓存友好（数组连续存储，CPU缓存预加载高效）,速度是所有O(n log n)算法中最快的。
  • 快排使用左右指针向中间遍历的方法，左右指针是顺序访问的，结合缓存预加载可以有效提高缓存命中率（缓存的数据都是活跃的,遍历完缓存在重新加载）
• 例：对内存中的10万条用户数据（按年龄排序），快排比归并排序、堆排更快。
• 标准库内置排序：大多数编程语言的标准库排序（如C++ std::sort、Python sorted、Java Arrays.sort）均以快排为基础（或结合其他算法优化）。
  例：用Python对列表[3,1,4,1,5]排序，底层调用的优化版快排（Timsort的部分逻辑）。
• 空间敏感场景：原地排序（仅需O(log n)递归栈空间），比归并排序（O(n)额外空间）更适合内存有限的场景。
  例：在手机APP中对本地存储的1万条聊天记录（按时间戳排序），快排无需额外内存存储临时数据。

致命缺点

• “最坏 O(n²) + 栈溢出”；数据有序且未随机选 pivot 时直接退化；递归深度可达 n，线程栈 1MB 时 n≈1w 就能爆栈，工程必须上 introsort 兜底。

七、归并排序（Merge Sort）

核心操作

1. 拆分（Divide）：将数组从中间二分，递归拆分为两个子数组，直到子数组长度为1（天然有序）；
2. 合并（Merge）：将两个有序子数组“有序合并”为一个大的有序数组（核心步骤）：
   • 开辟临时数组，双指针分别指向两个子数组的起始位置；
   • 比较指针指向的元素，将较小的元素放入临时数组，移动对应指针；
   • 遍历结束后，将剩余元素依次放入临时数组，再将临时数组拷贝回原数组；
3. 递归合并：重复“拆分→合并”，直到所有子数组合并为一个完整的有序数组。

复杂度

适合场景（含例子）

• 需要稳定排序的场景：归并排序是天然稳定的O(n log n)算法，适合多关键字排序（如“先按成绩排序，成绩相同按学号排序”）。
  例：对学生成绩单排序，要求“成绩降序，成绩相同的学生按学号升序”，归并排序可保证学号顺序不被打乱。
• 链表排序：链表的“指针操作”适配归并的“合并”步骤（无需移动元素，仅修改指针），空间复杂度可优化至O(1)，是链表排序的最优选择。
  例：对单链表存储的“商品列表”（按价格排序），归并排序比快排更高效。
• 外部排序（处理超内存数据）：可将数据拆分为多个磁盘文件（有序归并段），通过“多路归并”逐步合并，适合处理无法一次性加载到内存的大数据。
  例：对100GB的日志文件（按时间戳排序），用归并排序的思路分块排序后再合并，突破内存限制。

致命缺点

八、基数排序（Radix Sort）

核心操作

1. 确定基数和位数：选择“基数”（通常为10，即按十进制位排序），确定数据的最大位数（如数据[123,45,6]的最大位数为3）；
2. 按位排序（LSD/MSD）：
   • 低位优先（LSD）：从最低位（个位）开始，依次对每一位进行“计数排序”（稳定排序）；
   • 高位优先（MSD）：从最高位开始排序，递归处理每一位的子区间；
3. 迭代排序：完成所有位数的排序后，数组整体有序（因每一步的计数排序是稳定的，高位的排序结果会保留低位的有序性）。

复杂度

适合场景（含例子）

• 整数/字符串等“可按位拆分”的数据排序：无需比较元素大小，通过“按位分配”实现排序，适合数据范围大但位数少的场景。
  例：对100万个手机号码（11位数字，d=11，k=10）排序，基数排序的时间复杂度O(11×(1e6+10))≈O(1e7)，比快排（O(1e6 log 1e6)≈O(2e7)）更快。
• 大规模稳定排序场景：比归并排序的常数项更小（无递归，按位处理更简单），适合需要稳定排序且数据量大的场景。
  例：对电商平台的“订单号”（格式为“日期+序号”，如20240929001）排序，基数排序可按位处理，且保证相同日期的订单按序号有序。
• 多关键字排序：可将多个关键字拆分为“位”（如“年、月、日”对应三位基数），直接按位排序，无需嵌套排序。
  例：对日志的“时间戳”（年、月、日、时、分、秒）排序，按“秒→分→时→日→月→年”的低位优先顺序排序，直接得到按时间递增的结果。

致命缺点

八大排序算法核心差异总结

选择排序算法的核心原则：数据规模→稳定性需求→空间限制→数据分布，而非单纯追求“复杂度最优”。