《数据结构初阶》【八大排序——群英荟萃】

【八大排序——群英荟萃】目录

• 前言：
• • 什么是排序？排序在生活中有哪些应用？
  • 所谓的八大排序指的是哪八大排序呢？
  • 排序有哪些概念？
  • • 比较排序or非比较排序？
    • 稳定排序or非稳定排序？
    • 内部排序or外部排序？
• ---------------插入排序---------------
• • ---------------直接插入排序---------------
  • 直接插入排序是什么？
  • 直接插入排序的思想是什么？
  • 直接插入排序怎么使用代码实现？
  • 直接插入排序属性怎么样？
  • ---------------希尔排序---------------
  • 希尔排序是什么？
  • 希尔排序的思想是什么？
  • 希尔排序怎么使用代码实现？
  • 希尔排序的属性怎么样？
• ---------------选择排序---------------
• • ---------------简单选择排序---------------
  • 简单选择排序是什么？
  • 简单选择排序的思想是什么？
  • 简单选择排序怎么使用代码实现？
  • 简单选择排序的属性怎么样？
  • ---------------堆排序---------------
  • 堆排序是什么？
  • 堆排序的思想是什么？
  • 堆排序怎么使用代码实现？
  • 堆排序的属性怎么样？
• ---------------交换排序---------------
• • ---------------冒泡排序---------------
  • 冒泡排序是什么？
  • 冒泡排序的思想是什么？
  • 冒泡排序怎么使用代码实现？
  • 冒泡排序的属性怎么样？
  • ---------------快速排序---------------
  • 快速排序是什么？
  • 快速排序的思想是什么？
  • • hoare对撞指针分区算法
    • lomuto快慢指针分区算法
    • 挖坑分区算法
  • 快速排序怎么使用代码实现？
  • • 快速排序的递归实现
    • 快速排序的非递归实现
  • 快速排序的属性怎么样？
• ---------------归并排序---------------
• • ---------------归并排序---------------
  • 归并排序是什么？
  • 归并排序的思想是什么？
  • 归并排序怎么使用代码实现？
  • • 归并排序递归实现
    • 归并排序的非递归实现
  • 归并排序的属性怎么样？
• ---------------计数排序---------------
• • 计数排序是什么？
  • 计数排序的思想是什么？
  • • 简单实现的基本思想
    • 计数排序简单实现怎么使用代码实现？
    • 完整实现的基本思想
  • 计数排序的属性怎么样？
• ------------------------------
• • 八大排序的性能大总结

往期《数据结构初阶》回顾：
【时间复杂度 + 空间复杂度】
【顺序表 + 单链表 + 双向链表】
【顺序表/链表 精选15道OJ练习】
【顺序栈 + 链式队列 + 循环队列】
【链式二叉树】
【堆 + 堆排序 + TOP-K】
【二叉树 精选9道OJ练习】

前言：

小伙伴们 (✧ω✧) ～明天就是小满啦🌾 还记得我们上次学习栈和队列时候还是立夏呢。
不知不觉间，这15 天就悄然溜走啦🌤️。而我们《数据结构初阶》的学习也快要进入尾声咯，今天我们就要遇到咱们在新手村中遇到的最后一个大 boss 👾——八大排序 了，大家可得鼓足干劲，拿下这一关呀💪！

这次博主写这篇博客可花了不少时间呢，全文足有 1.5w 字～希望大家能耐心阅读 (●’◡’●) 。
要是一次看不完也没关系，点个收藏⭐慢慢品味就好啦，当然…如果能点个关注就更好啦 (〃‘▽’〃)

什么是排序？排序在生活中有哪些应用？

排序（Sorting）：是指将一组数据元素按照某种关键字（如：数值大小、字母顺序等）重新排列成有序序列的过程。

• 其核心目标是通过特定算法调整元素顺序，使最终序列满足升序（从小到大）或降序（从大到小）的要求。
• 排序在数据处理、搜索、优化算法等场景中具有广泛应用。
  • 例如：数据库查询优化、任务调度、数据可视化等。

想必大家看了上面对排序的介绍之后，对排序是什么已经有了更加清晰的了解，但是现实中排序算法真的像上面说的这么常见和重要吗？

那这里博主就简单举一个我们平时经常能看到的例子，比如：抖音的热搜榜。

（感慨一下：时间过得好快啊！）

所谓的八大排序指的是哪八大排序呢？

上面图片中用扁圆框标注的排序算法就是我们常说的 “八大排序”。当然，排序算法的种类远不止这八种，我们之所以着重学习这八种，是因为其他排序（如：基数排序、桶排序）在实际应用中较为少见，且实现相对复杂。

这是可能会有一些小伙伴们会问：“像冒泡排序这样的算法，难道在现实中应用很广泛吗？”

哈哈哈，确实像这样的简单排序算法在实际开发中几乎不会被使用。但它们的逻辑简单易懂，适合作为入门学习的过渡，所以我们还是用有必要进行学习的。

---

下面这个表格先简单的介绍一下八大排序的思想，后面会有不同的模块进行详细的介绍：

排序算法 思想描述 直接插入排序 将未排序元素逐个插入到已排序部分的正确位置 希尔排序 改进的插入排序，按动态间隔分组后逐步缩小组距至1 简单选择排序 每次选择未排序部分的最小元素，放到已排序末尾 堆排序 利用堆结构（完全二叉树）进行选择排序 冒泡排序 重复比较相邻元素，将较大元素逐步“冒泡”到末尾 快速排序 分治法，选一个基准（pivot）将数组分为两部分递归排序 归并排序 分治法，将数组分成两半分别排序后合并 计数排序 统计每个元素的出现次数，按计数顺序输出

排序有哪些概念？

现在大家可以回想一下，上面的那张图片将八大排序分成了哪两部分呢？

对，就是：比较排序和非比较排序

其实呢，除了上面的这种划分方式，你还可以，简单粗暴将所有的排序分为：

1. 内排序和外排序
2. 稳定排序和非稳定排序

下面我们将介绍一下这些名词是什么意思？以及它们划分依据是什么？

比较排序or非比较排序？

在排序算法中，比较排序 和 非比较排序 是根据排序的核心逻辑是否依赖 “元素间比较” 来划分的两类算法。

---

比较排序（Comparison Sort）：通过比较元素之间的大小关系来确定它们的顺序，所有操作均基于比较结果进行。

核心特点：

1. 依赖比较操作：排序过程中，必须通过 a > b、a < b 或 a == b 等比较运算符来决定元素位置。
2. 通用适用性：适用于任意类型的数据（只要能定义大小比较规则）
   • 例如：整数、字符串、自定义对象等。
3. 时间复杂度下限：
   • 对于 基于比较的排序算法，其时间复杂度的理论下限为 $O(nlogn)$（在最坏情况下，任何比较排序都无法突破这个下限）。
   • 例外：部分简单排序（如：直接插入排序、简单选择排序、冒泡排序）的最坏时间复杂度为 O ( n 2 ) O(n^2) O(n2)，但它们仍属于比较排序。
4. 常见算法：
   • 简单比较排序：直接插入排序、简单选择排序、冒泡排序
   • 高效比较排序：希尔排序、堆排序、快速排序、归并排序

---

非比较排序（Non-Comparison Sort）：不依赖元素间的比较，而是利用元素值的特性或统计信息（如：数值范围、出现频率）直接计算元素的位置。

核心特点：

1. 不进行比较操作：通过数学方法（如：映射、统计）直接确定元素顺序。
2. 数据局限性：仅适用于特定类型的数据（通常为整数或可映射为整数的类型），例如：
   • 数值范围有限（如： 0 ≤ a i ≤ 100 0 \\leq a_i \\leq 100 0≤ai​≤100）
   • 可分解为独立数位（如：基数排序处理多位数）
3. 时间复杂度优势：
   • 多数非比较排序的时间复杂度为 $O(n)$ 或 $O(n+k)$（$k$ 为数据范围），优于比较排序的理论下限。
   • 代价：需额外空间或数据满足特定条件
4. 常见算法：
   • 计数排序（Counting Sort）：统计每个值的出现次数，直接映射到结果数组。
   • 基数排序（Radix Sort）：按数位从低到高排序，利用桶分组实现。
   • 桶排序（Bucket Sort）：将数据分配到有限数量的桶中，对每个桶内数据排序后合并。

---

稳定排序or非稳定排序？

在排序算法中，稳定排序（Stable Sort） 和 非稳定排序（Unstable Sort）是根据排序过程中相等元素的相对顺序是否保持不变来区分的重要属性。

---

稳定排序（Stable Sort）：当待排序序列中存在值相等的元素时，排序后这些元素的相对顺序与排序前一致。

• 核心条件：若 a i = a ja_i = a_j ai​=aj​ 且在排序前 a ia_i ai​ 出现在 a ja_j aj​ 前面，则排序后 a ia_i ai​ 仍在 a ja_j aj​ 前面。

核心特点：

1. 保留相等元素顺序：适用于需要维护 “次要关键字” 的场景（如：多关键字排序）
2. 典型算法：
   • 直接插入排序：插入时从后往前查找位置，相等元素不会被移动到前面。
   • 冒泡排序：相邻元素交换时，仅当前者大于后者才交换，相等元素不移动。
   • 归并排序：合并子数组时，按顺序保留相等元素的原始顺序。
   • 计数排序：非比较排序中典型的稳定排序，通过统计频率确保相等元素顺序。

场景示例：对学生成绩表按 “分数” 排序，若分数相同，需保留 “原始录入顺序”（次要关键字）

• 排序前数据（姓名，分数）： (Alice, 80), (Bob, 85), (Charlie, 80), (David, 90)
• 稳定排序结果： 按分数升序排序后，两个 80 分的学生顺序不变： (Alice, 80), (Charlie, 80), (Bob, 85), (David, 90)

---

非稳定排序（Unstable Sort）：排序后，相等元素的相对顺序可能改变（即：可能打乱排序前的顺序）。

• 核心特征：不保证相等元素的原始顺序，可能因算法实现中的 “随机交换” 或 “非顺序处理” 导致顺序变化。

核心特点：

1. 可能打乱相等元素顺序：适用于仅需关注主关键字，无需保留次要信息的场景。
2. 典型算法：
   • 简单选择排序：每次选择最小元素与当前位置交换，可能交换相等元素的位置。
   • 希尔排序：分组插入的特性可能破坏相等元素的原始顺序。
   • 堆排序：堆的调整过程中，相等元素可能被非顺序地取出。
   • 快速排序：基准元素的选择和分区逻辑可能导致相等元素顺序变化。

场景示例：同上例，使用非稳定排序（如：选择排序）

• 排序前数据：(Alice, 80), (Bob, 85), (Charlie, 80), (David, 90)
• 非稳定排序结果： 分数升序排序后，两个 80 分的学生顺序可能变为 Charlie 在 Alice 前面（因选择排序可能先找到 Charlie 作为最小元素）： (Charlie, 80), (Alice, 80), (Bob, 85), (David, 90)

内部排序or外部排序？

在排序算法中，内部排序（Internal Sorting） 和 外部排序（External Sorting）是根据数据处理时数据是否完全加载到内存中来划分的两类方法。

---

内部排序（Internal Sorting）：数据完全存储在内存中，排序过程中所有操作都在内存中完成，无需频繁访问外部存储（如：硬盘）

• 适用场景：数据量较小，能被内存容纳（通常为几十 MB 到几百 MB 级别）

核心特点：

1. 数据在内存中处理：速度快，依赖内存的随机访问特性。
2. 算法多样性：包含多种经典算法，根据时间复杂度、稳定性等特性适用于不同场景。
3. 常见算法：
   • 比较排序：插入排序、选择排序、冒泡排序、希尔排序、堆排序、快速排序、归并排序等
   • 非比较排序：计数排序、基数排序、桶排序等（依赖数据范围或分布特性）
4. 性能瓶颈：受内存容量限制，数据量超过内存大小时无法直接使用。

---

外部排序（External Sorting）：数据量远超内存容量，无法一次性加载到内存中，需借助外部存储（如：硬盘、U 盘等），通过内存与外存的多次数据交换完成排序。

• 适用场景：处理大规模数据（如：GB、TB 级别），常见于数据库、日志分析等场景。

核心特点：

1. 数据分块处理：

   • 将数据分割成多个 块（Block），每次仅加载部分数据到内存中排序（称为： “归并段”）
   • 排序后的归并段写回外存，最后通过归并算法合并所有有序段。

2. 依赖外存读写效率：

   • 外存（如：硬盘）的读写速度远低于内存（通常慢 10 万倍以上），因此减少 IO 次数是优化关键。

3. 经典算法：多路归并排序

   • 步骤 1：生成初始归并段
     将数据分块读入内存，用内部排序生成有序段，写回外存。

   • 步骤 2：多路归并

     每次从多个有序段中读取部分数据到内存，合并成一个更大的有序段，重复直至所有数据有序。

     • 例如：若内存可容纳 2 个块，则使用 2 路归并；若可容纳 k 个块，则使用 k 路归并（k 越大，IO 次数越少）

4. 辅助结构：

   • 利用败者树或优先队列优化归并过程中的数据选取，减少内存占用。

---------------插入排序---------------

---------------直接插入排序---------------

直接插入排序是什么？

直接插入排序（Straight Insertion Sort）：是一种简单直观的内部排序算法，属于插入排序的一种。

• 它的核心思想是：将待排序元素逐个插入到已排序序列的合适位置，类似于日常生活中整理扑克牌的过程。

直接插入排序的思想是什么？

直接插入排序的基本思想：

1. 已排序区间与未排序区间：
   • 假设数组分为两部分：左侧是已排序好的子序列，右侧是待排序的子序列。
   • 初始时，已排序区间仅包含第一个元素（单个元素默认有序），未排序区间包含剩余元素。
2. 逐个插入过程：
   • 从未排序区间中取出第一个元素，在已排序区间中从后往前比较，找到合适的插入位置，将该元素插入并保持已排序区间有序。
   • 重复此过程，直到所有元素都被插入到已排序区间中。

直接插入排序怎么使用代码实现？

void InsertSort(int* a, int n){//1.外层的循环控制 ---> 记录当前数组中区间到那里已经是有序的了 （解释：循环变量i=n-2意味着“当前数组中区间为[0,n-1]范围中的元素现在已经是有序的了”）for (int i = 0; i <= n - 2; i++) //注：i虽然只能到n-2的但是当i=n-2的时候，我们正在处理的是下标为n-1位置的元素,也就是数组中的最后哦一个元素{//2.记录当前数组中已经有序区间的右下标int end = i;//3.取出我们要进行插入排序的元素int tmp = a[end + 1];//4.内层的循环控制 ---> 寻找我们要插入的位置while (end >= 0){//核心：前面元素的值大进行后移if (a[end] > tmp){a[end + 1] = a[end];end--;}else{break;}}//注意：因为end的值变为-1而退出的while循环的情况：意味着当前处理的这个元素的值比数组中区间为[0,end]的已经有序元素的任意一个元素的值都要小a[end + 1] = tmp;}}

直接插入排序属性怎么样？

关于直接插入排序属性的大总结：

属性 分析结果 时间复杂度 最坏： O ( n 2 ) O(n^2) O(n2)（逆序数据）
最好：$O(n)$（已有序数据）
平均： O ( n 2 ) O(n^2) O(n2) 空间复杂度 $O(1)$（原地排序，仅需常数额外空间） 稳定性 稳定排序 适用场景 小规模数据$n<50$
基本有序的数据
链表排序
复杂算法的子过程优化

---------------希尔排序---------------

希尔排序是什么？

希尔排序（Shell Sort）：也称为缩小增量排序（Diminishing Increment Sort），是直接插入排序的一种改进版本。

• 它的核心思想是：通过分组插入的方式，优先处理距离较远的元素，从而减少元素移动次数，显著提升排序效率。

希尔排序的思想是什么？

希尔排序的基本思想：

1. 分组插入
   • 将原始数组按固定间隔（增量） 分成多个子数组，对每个子数组分别进行直接插入排序。
   • 随着排序进行，逐步缩小增量，直到增量为 1 时，整个数组被视为一个子数组，执行最后一次插入排序（此时数组已接近有序，效率较高）
2. 核心原理
   • 通过大步长移动元素，快速将元素放到接近最终位置的地方，减少后续小步长插入时的移动次数。

初始状态：数组初始序列为 9 1 2 5 7 4 8 6 3 5

第一趟排序（gap = 5）

1. 分组规则：间隔gap = 5，将数组分为 5 组 ，分别是：
   • 第一组：第 1 个元素和第 6 个元素，即 9 和 4
   • 第二组：第 2 个元素和第 7 个元素，即 1 和 8
   • 第三组：第 3 个元素和第 8 个元素，即 2 和 6
   • 第四组：第 4 个元素和第 9 个元素，即 5 和 3
   • 第五组：第 5 个元素和第 10 个元素，即 7 和 5
2. 组内排序：对每组进行直接插入排序 ，排序规则是将每组中第二个元素与第一个元素比较，若小于第一个元素则交换位置。
   • 第一组：4 < 9 ，交换后为 4
   • 第二组：1 < 8 ，顺序不变，仍为 1
   • 第三组：2 < 6 ，顺序不变，仍为 2
   • 第四组：3 < 5 ，交换后为 3
   • 第五组：5 < 7 ，交换后为 5
3. 排序结果：经过第一趟排序，数组变为 4 1 2 3 5 9 8 6 5 7

---

第二趟排序（gap = 2）

1. 分组规则：间隔gap = 2，将数组分为 2 组 ，分别是：

   • 第一组：第 1、3、5、7、9 个元素，即 4 2 5 8 5
   • 第二组：第 2、4、6、8、10 个元素，即 1 3 9 6 7

2. 组内排序：对每组进行直接插入排序，从第二个元素开始，与前面已排序元素比较并插入到合适位置。

   第一组：（子序列：[4, 2, 5, 8, 5]）

   1. 初始：[4, 2, 5, 8, 5]

      • 已排序部分：[4]
      • 待插入：[2, 5, 8, 5]

   2. 插入2：比较 2 和 4 → 2 < 4 → 移动 4 → 插入 2

      • 操作：[ (2), 4, 5, 8, 5 ]
      • 结果：[2, 4, 5, 8, 5]

   3. 插入5：比较 5 和 4 → 5 > 4 → 不移动

      • 结果：[2, 4, 5, 8, 5]

   4. 插入8：比较 8 和 5 → 8 > 5 → 不移动

      • 结果：[2, 4, 5, 8, 5]

   5. 插入5：

      • 比较 5 和 8 → 5 < 8 → 移动 8 → [2, 4, 5, ( ), 8]
      • 比较 5 和 5 → 5 == 5 → 不移动（保持插入排序的稳定性）
      • 插入 5
      • 操作：[2, 4, 5, (5), 8]

      最终组1：[2, 4, 5, 5, 8]

   ---

   第二组：（子序列：[1, 3, 9, 6, 7]）

   • 初始：[1, 3, 9, 6, 7]

     • 已排序部分：[1]
     • 待插入：[3, 9, 6, 7]

   • 插入3：比较 3 和 1 → 3 > 1 → 不移动

     • 结果：[1, 3, 9, 6, 7]

   • 插入9：比较 9 和 3 → 9 > 3 → 不移动

     • 结果：[1, 3, 9, 6, 7]

   • 插入6：

     • 比较 6 和 9 → 6 < 9 → 移动 9 → [1, 3, ( ), 9, 7]
     • 比较 6 和 3 → 6 > 3 → 不移动
     • 插入 6
     • 操作：[1, 3, (6), 9, 7]
     • 结果：[1, 3, 6, 9, 7]

   • 插入7：

     • 比较 7 和 9 → 7 < 9 → 移动 9 → [1, 3, 6, ( ), 9]
     • 比较 7 和 6 → 7 > 6 → 不移动
     • 插入 7
     • 操作：[1, 3, 6, (7), 9]

     最终组2：[1, 3, 6, 7, 9]

---

将排序后的子序列按原始索引位置填回：

• 组1：[2, 4, 5, 5, 8] → 索引 0, 2, 4, 6, 8
• 组2：[1, 3, 6, 7, 9] → 索引 1, 3, 5, 7, 9

索引： 0 1 2 3 4 5 6 7 8 9值： [2, 1, 4, 3, 5, 6, 5, 7, 8, 9]

排序结果：经过第二趟排序，数组变为 2 1 4 3 5 6 5 7 8 9

---

第三趟排序（gap = 1）

1. 分组规则：间隔 gap = 1 ，此时整个数组视为一组，即 2 1 4 3 5 6 5 7 8 9
2. 组内排序：进行直接插入排序，从第二个元素 1 开始，依次与前面元素比较并插入到合适位置。经过多次比较和交换后，最终数组变为有序数组 1 2 3 4 5 5 6 7 8 9

希尔排序怎么使用代码实现？

void ShellSort(int* a, int n){//1.初始化间隔为数组的长度int gap = n;//2.第一层循环 ---> 动态的调整间隔的序列while (gap > 1){// 计算新的间隔，使用Knuth提出的序列：h = h/3 + 1 （这个序列在实践中表现较好）gap = gap / 3 + 1;//注：接下来的实现主要有两种实现的方式：分别是：//1.严格分组法//2.交叉分组法//注：这两种方法性能上没有什么明显的区别，只是交叉分组法更加简洁，大多数的人都使用交叉分组法/*--------------------------展示：严格分组法--------------------------*//*//第二层循环 ---> 控制我们处理组for (int group = 0; group  控制已排序区间的右边界for (int i = group; i  寻找我们要插入的位置while (end >= 0){//核心：前面的元素的值大时进行后移if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}*//*--------------------------展示：交叉分组法--------------------------*///第二层循环 ---> 控制已排序区间的右边界for (int i = 0; i <= n - gap - 1; i++){int end = i;int tmp = a[end + gap];//第三层循环 ---> 寻找我们要插入的位置while (end >= 0){//核心：当前面的元素的值大进行后移if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}}

希尔排序的属性怎么样？

关于希尔排序属性的大总结：

特性 描述 时间复杂度 最坏：取决于增量序列，希尔增量为 O ( n 2 ) O(n^2) O(n2)，Knuth 增量约为 O ( n 1.3 ) O(n^{1.3}) O(n1.3)
最好：$O(nlogn)$ 空间复杂度 $O(1)$ 稳定性 不稳定排序 适用场景 中等规模数据排序
内存受限场景
对效率有一定要求但实现简单的排序需求

---------------选择排序---------------

---------------简单选择排序---------------

简单选择排序是什么？

简单选择排序（Simple Selection Sort）：是一种简单直观的内部排序算法 。

• 它的核心思想是：每次从未排序部分选出最小（或最大）元素，放到已排序部分的末尾，直到所有元素有序。

简单选择排序的思想是什么？

简单选择排序的基本思想：

1. 已排序区间与未排序区间划分：
   • 将待排序序列视为左右两部分：左侧为已排序区间（初始为空），右侧为未排序区间（包含所有元素）
   • 初始状态下，已排序区间长度为 0，未排序区间为整个序列。
2. 选择与交换过程：
   • 每次从未排序区间中查找最小元素，并将其与未排序区间的首元素交换位置，使该最小元素加入已排序区间。
   • 未排序区间长度减 1，已排序区间长度增 1，重复此操作直至未排序区间为空。
3. 排序终止条件：
   • 当未排序区间元素个数为 0 时，整个序列完成排序，已排序区间包含所有元素且有序。

简单选择排序怎么使用代码实现？

void SelectSort(int* a, int n){//1.记录选择排序的区间边界（解释：在区间之外的元素已经有序）//注：这里进行了优化，原始的直接选择排序进行一个次排序只会找到未排序区间中的最小的元素，这里优化为一次可以找到：最大的元素和最小的元素int begin = 0, end = n - 1;//2.记录区间内值最大和最小的元素的下标int minn, maxx;//3.外层循环 ---> 控制已排序区间的左右边界 （解释：beigin=3,end=n-4代表：数组中下标为[3,n-4]这个区间的中的元素还没有进行排序）while (begin < end){//4.初始化当前数组未排序区间中元素的最大值和最小值元素的下标为beginminn = begin, maxx = begin;//5.内层循环 ---> 寻找未排序区间中实际的最小/最大值索引for (int i = begin + 1; i <= end; i++){//5.1：更新最小值的索引if (a[i] < a[minn]){minn = i;}//5.2：更新最大值的索引if (a[i] > a[maxx]){maxx = i;}}//6.进行元素位置的交换//6.1：将最小值交换到区间的头部Swap(&a[minn], &a[begin]);//6.2：修正最大值在数组中的下表中的位置/* 关键修正：处理最大值正好在begin位置的特殊情况 * 因为先交换了begin和minn，可能导致maxx指向的值被移动 * 例子：[5, 3, 1, 4, 2]中： * - 第一轮begin=0, maxx=0, minn=2 * - 交换begin和minn后变为[1, 3, 5, 4, 2] * - 此时原maxx=0的值已被移动到minn=2的位置 */if (maxx == begin){maxx = minn;}//6.3：将最大值交换到区间的尾部Swap(&a[maxx], &a[end]);//7.缩小未排序区间begin++;end--;}}

注：简单选择排序使用了其他的辅助函数：

1. 交换函数

void Swap(int* a, int* b){int tmp = *a;*a = *b;*b = tmp;}

简单选择排序的属性怎么样？

关于简单选择排序属性的大总结：

属性 分析结果 时间复杂度 最坏： O ( n 2 ) O(n^2) O(n2)（任意顺序均需遍历未排序区间）
最好： O ( n 2 ) O(n^2) O(n2)（已有序数据仍需遍历）
平均： O ( n 2 ) O(n^2) O(n2) 空间复杂度 $O(1)$ 稳定性 不稳定排序 适用场景 小规模数据（效率低于插入排序）
对稳定性无要求的场景

---------------堆排序---------------

堆排序是什么？

堆排序（Heap Sort）：是一种基于堆数据结构的排序算法，属于选择排序的变种。

• 它的核心思想是：通过构建堆来实现数据的排序，核心思想是利用堆的性质高效地选择当前未排序元素中的最大值或最小值，从而逐步完成排序。

堆排序的思想是什么？

堆排序的基本思想：

1. 堆的定义与分类
   • 堆是一种完全二叉树，满足以下性质：
     • 大根堆：每个节点的值都大于或等于其子节点的值（根节点为最大值）
     • 小根堆：每个节点的值都小于或等于其子节点的值（根节点为最小值）
2. 排序过程
   • 步骤 1：构建初始堆
     将待排序数组构造成一个大根堆（升序排序）或小根堆（降序排序）。
     • 此时，堆顶元素为整个数组的最大值或最小值。
   • 步骤 2：交换堆顶与末尾元素
     将堆顶元素（最大值 / 最小值）与堆的最后一个元素交换位置。
     • 此时，末尾元素为已排序的最大值 / 最小值，剩余元素构成新的未排序堆。
   • 步骤 3：调整堆结构
     对交换后的堆（规模减 1）重新调整，使其再次满足堆的性质。
     • 此后，重复步骤 2 和步骤 3，直到堆中只剩一个元素，排序完成。

堆排序怎么使用代码实现？

void HeapSort(int* a, int n){/*------------------第一阶段：建堆------------------*///建堆的方法有两种：//1.向上调整建堆//2.向下调整建堆//注：这两种方法有明显的性能差别，向下调整建堆算法的时间复杂度更小，使用的人也更多//建堆本质：从堆中最后一个非叶子节点到堆顶节点逐个使用：向下调整算法for (int i = (n - 1 - 1) >> 1; i >= 0; i--){AdjustDown(a, i, n);}/*------------------第二阶段：将堆顶元素与末尾的元素进行交换 + 向下调整堆------------------*///1.定义一个变量记录当前堆中最后一个元素的在数组中的索引int end = n - 1;//2.循环进行第二阶段直到堆对应的数组中只剩下标为0的元素的值还没用进行交换的时候while (end > 0){//2.1：将堆顶元素与末尾的元素进行交换Swap(&a[0], &a[end]);//2.2：更新堆对应数组的容量 ---> （逻辑上：删除了堆顶元素）end--;//2.3：重新向下调整堆AdjustDown(a, 0, end + 1);}}

注：堆排序使用了其他的辅助函数：

1. 向下调整函数
2. 交换函数

---------------------------------向下调整函数---------------------------------void AdjustDown(int* a, int parent, int n){//思路：向下调整的本质：是判断父节点的值和左右孩子的值的大小关系，并将父子关系不满足大根堆条件（孩子大于父亲）的情况进行交换调整//所以我任务是//任务1：找到父节点孩子中值最大的那个孩子//任务2：判断父节点和孩子节点的大小关系，并进行调整//1.先假设父节点的左孩子是值最大的孩子int maxChild = (parent << 1) + 1;//注意1：这里还用+1，因为这里是maxChild 和 parent 都是数组的下标//注意2：位运算符的优先级比算数运算符的优先级小 ---> 一般情况下：如果位运算符我们不写在表达式的最后的话，都要添加()来提高优先级//2.循环进行交换调整while (maxChild < n) //当孩子的索引值 >= n 的时候，说明进行调整到不能在调整了{//3.确定父节点的值最大的孩子节点if (maxChild + 1 < n && a[maxChild + 1] > a[maxChild]){maxChild = maxChild + 1;}//4.判断父节点和孩子节点的大小关系if (a[parent] >= a[maxChild]) return;else{//4.1: 交换Swap(&a[parent], &a[maxChild]);//4.2：更新parent = maxChild;//4.3：寻找maxChild = (parent << 1) + 1;}}}

-----------------------------------交换函数----------------------------------- void Swap(int* a, int* b){int tmp = *a;*a = *b;*b = tmp;}

堆排序的属性怎么样？

关于堆排序属性的大总结：

属性 分析结果 时间复杂度 最坏：$O(nlogn)$
最好：$O(nlogn)$
平均：$O(nlogn)$ 空间复杂度 $O(1)$ 稳定性 不稳定排序 适用场景 大规模数据排序
无需额外空间的场景
不适用于稳定性要求高的场景

---------------交换排序---------------

---------------冒泡排序---------------

冒泡排序是什么？

冒泡排序（Bubble Sort）：是最基础的排序算法之一。

• 它的核心思想是：通过 重复比较相邻元素并交换位置，将较大的元素逐步“浮”到数组末端，如同气泡上浮，因此得名。

冒泡排序的思想是什么？

冒泡排序的基本思想：

1. 已排序区间与未排序区间划分：
   • 将数组视为左右两部分：右侧为已排序区间（初始为空），左侧为未排序区间（包含所有元素）
   • 初始时，已排序区间长度为 0，未排序区间为整个数组
2. 相邻元素比较与交换：
   • 从未排序区间的头部（数组起始位置）开始，依次比较相邻元素：
     • 若前一个元素大于后一个元素（升序场景），则交换两者位置
     • 每轮遍历后，未排序区间的最大元素会 “冒泡” 到未排序区间的末尾，同时已排序区间长度增 1
3. 排序终止条件：
   • 重复相邻元素比较过程，直到未排序区间长度为 1（此时已排序区间包含前 $n-1$ 个元素，且最后一个元素为最小值），整个数组完成排序

冒泡排序怎么使用代码实现？

void BubbleSort(int* a, int n){//1.外层的循环控制 ---> 记录需要进行交换的数字的个数[“也可理解为冒泡的总的趟数”]（解释：n个数字只需要对n-1个数字进行排序即可实现n个数字的有序）for (int i = 1; i <= n - 1; i++){//2.内层的循环控制 ---> 记录对每个数字进行排序需要交换的次数[“也可以理解为每趟冒泡需要交换的次数”]（注意：每趟冒泡需要交换的次数是不同的）//每趟冒泡需要交换的次数会逐渐的减少，次数类似于一个等差数列，例如：n个元素的一个数组//第一趟的冒泡需要比较的次数：n-1//第二趟的冒泡需要比较的次数：n-2//第三趟的冒泡需要比较的次数：n-3 （总结：每趟冒泡需要交换的次数为 = 元素的总个数n - 这是冒泡的第几趟i）//………………………………//第n-2趟的冒泡需要比较的次数：2//第n-1趟的冒泡需要比较的次数：1//对冒泡排序进行优化：int flag = 1;for (int j = 1; j <= n - i; j++){//核心：前面的元素的值大进行交换if (a[j - 1] > a[j]){Swap(a[j - 1], a[j]);flag = 0;}}if (flag) break; //如果某一趟的冒没有进行交换，说明当前数组中的元素已经有序了，则直接退出}}

注：冒泡排序使用了其他的辅助函数：

1. 交换函数

void Swap(int* a, int* b){int tmp = *a;*a = *b;*b = tmp;}

冒泡排序的属性怎么样？

关于冒泡排序属性的大总结：

属性 分析结果 时间复杂度 最坏： O ( n 2 ) O(n^2) O(n2)（逆序数据）
最好：$O(n)$（已有序数据）
平均： O ( n 2 ) O(n^2) O(n2) 空间复杂度 $O(1)$ 稳定性 稳定排序 适用场景 小规模数据
基本有序的数据
教育场景（直观易理解）

---------------快速排序---------------

快速排序是什么？

快速排序（Quick Sort）：是一种基于 分治思想（Divide and Conquer） 的高效排序算法，通过递归地将数组划分为更小的子数组来实现排序。

• 它的核心思想是：利用基准元素（Pivot） 将数组分成两部分，使左侧元素都小于等于基准，右侧元素都大于等于基准，然后递归处理左右子数组。
• 快速排序由Tony Hoare于1959年提出，长期占据实际应用中的性能霸主地位。

快速排序的思想是什么？

在学习快速排序之前，我们需要先知道快速排序的核心是：分区算法

分区算法：将数组区间按照基准值划分为左右两部分，使得左侧所有元素小于等于基准值，右侧所有元素大于等于基准值。

下面我们将会详细介绍以下这三种常见的分区算法：

1. hoare对撞指针分区算法
2. lomuto快慢指针分区算法
3. 挖坑分区算法

hoare对撞指针分区算法

算法思想步骤：

1. 基准值选择：

   • 直接选择左边界元素作为基准值 key（即：a[left]）
     • 注意：代码中 key 存储的是基准值的下标（即：left），而非值本身

2. 指针初始化：

   • begin = left：左指针从区间左边界开始，向右扫描
   • end = right：右指针从区间右边界开始，向左扫描

3. 双指针扫描与交换：

   • 外层循环：只要 begin < end，继续扫描。

   • 右指针左移：

     while (begin < end && a[end] >= a[key]) { end--; }

     从右向左找第一个小于基准值的元素（即：a[end] < a[key]）

   • 左指针右移：

     while (begin < end && a[begin] <= a[key]) { begin++; }

     从左向右找第一个大于基准值的元素（即：a[begin] > a[key]）

   • 元素交换：
     当左右指针都停止时，交换 a[begin] 和 a[end]，将较小元素移到左边，较大元素移到右边。

4. 基准值归位：

   • 当 begin 和 end 相遇时（即：begin == end），此时相遇位置的元素小于等于基准值
     • 因为：右指针 end 先走，所以最终两个指针会相遇在end指针停下的位置，一个小于基准值的元素的位置
   • 将基准值 a[key] 与相遇位置的元素 a[begin] 交换，使得基准值左侧元素均 ≤ 基准值，右侧元素均 ≥ 基准值。

5. 返回基准值位置：

   • 返回 begin（或 end）作为分区点，用于后续递归处理左右子数组。

/*----------------------hoare对撞指针分区算法（未进行优化）----------------------*/int PartSort1(int* a, int left, int right){//1.直接选择左边界的元素作为基准值int key = left;//2.定义两个临时变量从区间的两端向中间进行扫描 ---> 高效地将数组分为两部分//使得一部分元素小于等于基准值，另一部分元素大于等于基准值，进而将基准值放置到其最终排序位置上int begin = left, end = right;//3.使用双边循环法分区while (begin < end){//3.1：从右向左寻找第一个小于基准的值while (begin < end && a[end] >= a[key]){end--;}//3.2：从左向右寻找第一个大于基准的值while (begin < end && a[begin] <= a[key]){begin++;}//3.4：交换这两个不符合条件的元素Swap(&a[begin], &a[end]);}//4.将基准值放到正确的位置（此时begin == end）Swap(&a[key], &a[begin]);//5.返回当前基准值的下标return begin;}

lomuto快慢指针分区算法

算法思想步骤：

1. 基准值选择优化
   • 使用三数取中法（GetMid函数）从区间[left, right]中选择中间值作为基准值，避免极端情况下的性能退化（如：已排序数组）
   • 将基准值交换到左边界left，便于后续处理
2. 指针初始化
   • key = left：记录基准值的索引。
   • slow = left：慢指针，标记小于基准值的元素区的右边界。
   • fast = left + 1：快指针，负责遍历整个区间。
3. 快慢指针扫描与交换
   • 外层循环：快指针fast从left+1开始遍历到right
   • 条件判断：若当前元素a[fast]小于基准值a[key]，则：
     • 慢指针slow右移一位（扩大小于基准值的元素区）
     • 交换a[fast]与a[slow]，将较小元素移至左侧
4. 基准值归位
   • 遍历结束后，slow指向最后一个小于基准值的元素
   • 将基准值a[key]与a[slow]交换，使基准值左侧元素均小于它，右侧元素均大于等于它
5. 返回分区点
   • 返回slow作为新的分区点，用于后续递归处理左右子数组

/*----------------------------lomuto快慢指针分区算法----------------------------*/int PartSort2(int* a, int left, int right){//1.进行三数取中优化：基准值的选取int mid = GetMid(a, left, right);//2.将找到的基准值放在左边界Swap(&a[left], &a[mid]);//3.定义一个变量记录基准值的索引int key = left;//4.定义一个慢指针：用于指向最后一个小于基准值的元素int slow = left;//5.定义一个快指针：用于扫描整个分区int fast = slow + 1;//6.进行分区while (fast <= right){if (a[fast] < a[key] && ++slow != fast){Swap(&a[fast], &a[slow]);}fast++;}//7.将基准值交换到最终的位置（此时slow指向最后一个小于基准的元素）Swap(&a[key], &a[slow]);//8.返回当前基准值的下标return slow;}

挖坑分区算法

算法思想步骤：

1. 基准值选择与初始化
   • 三数取中：通过GetMid函数选择left、right、中间位置三者的中间值作为基准值，避免极端情况
   • 交换基准值到左边界：将选中的基准值交换到数组左边界left
   • 保存基准值：key = a[left]，直接存储基准值而非下标（因为：后续坑位移动会改变原下标位置）
   • 初始化坑位：hole = left，初始坑位为基准值所在位置
2. 双指针扫描与填坑
   • 右指针左移：从右向左找第一个小于基准值的元素（a[end] < key），将其填入当前坑位hole，并更新坑位为end
   • 左指针右移：从左向右找第一个大于基准值的元素（a[begin] > key），将其填入当前坑位hole，并更新坑位为begin
   • 循环执行：重复上述过程，直到begin与end相遇
3. 基准值归位
   • 当begin与end相遇时，将基准值key填入最终坑位hole，此时基准值左侧元素均≤基准值，右侧元素均≥基准值。
4. 返回分区点
   • 返回hole作为新的分区点，用于后续递归处理左右子数组。

/*--------------------------------挖坑分区算法--------------------------------*/int PartSort3(int* a, int left, int right){//1.进行三数取中优化：基准值的选取int mid = GetMid(a, left, right);//2.将找到的基准值放在左边界Swap(&a[left], &a[mid]);//3.定义一个变量记录基准值(注意这里保存值而不是索引)int key = a[left]; //特别注意：这的key存储的不再是基准值的下标，而是直接存储的基准值，这是为什么呢？（下面的注释博主有详细的解释，请继续往下看……）//4.定义一个变量记录坑位int hole = left;//5.定义两个临时变量从区间的两端向中间进行扫描 ---> 高效地将数组分为两部分int begin = left, end = right;//6.进行分区while (begin < end){//6.1：从右向左寻找第一个小于基准的值while (begin < end && a[end] >= key){end--;}//6.2：找到后填左坑，end成为新坑 a[hole] = a[end]; //特别注意：这里while循环结束后并不是紧接又是一个while循环，而是做填坑、挖坑的操作，也恰恰是这个填坑、挖坑的操作使得基准值的下标已经发生了改变hole = end; //所以说：我们下面就不可以使用a[key]（假设：key存储的还是基准值的下标）的方式来得到基准值了，//6.3：从左向右寻找第一个大于基准的值while (begin < end && a[begin] <= key){begin++;}//6.4：找到后填右坑，left成为新坑a[hole] = a[begin];hole = begin;}//7.最后将基准值填入最后的坑位a[hole] = key;//8.返回当前基准值的下标return hole;}

注：上面的三种分区算法都要使用辅助函数：

1. 三数取中函数
2. 交换函数

---------------------------------三数取中函数---------------------------------int GetMid(int* a, int left, int right){//1.计算中间值int mid = (left + right) >> 1;//2.处理情况1：a[left] < a[mid]if (a[left] < a[mid]){if (a[right] < a[left]){return left;}else if (a[right] > a[mid]){return mid;}elsereturn right;}//3.处理情况2：a[left] > a[mid]else{if (a[right] > a[left]){return left;}else if (a[right] < a[mid]){return mid;}elsereturn right;}}

-----------------------------------交换函数-----------------------------------void Swap(int* a, int* b){int tmp = *a;*a = *b;*b = tmp;}

快速排序怎么使用代码实现？

快速排序的递归实现

/*---------------------------快排主函数（递归实现）---------------------------*/void QuickSort(int* a, int left, int right){//1.递归终止条件if (left >= right) return;//2.可以根据需要选择性的在这里添加小区间优化（比如：之前已经实现过了插入排序就可以在这里进行小区间优化了）//3.定义一个变量接收基准值的位置 int key = PartSort3(a, left, right); //注：这里你可以使用你之前实现的任意的一个分区算法//4.递归排序左右子区间QuickSort(a, left, key - 1);QuickSort(a, key + 1, right);}

快速排序的非递归实现

/*-----------------------------快排排序（非递归实现）-----------------------------*/void QuickSortNonR(int* a, int left, int right){/*---------------第一阶段：准备数据阶段---------------*///1.创建栈 + 初始化栈STK stk;STKInit(&stk);//2.先将整个数组区间压栈（注意顺序：先右后左）STKPush(&stk, right);STKPush(&stk, left);/*---------------第二阶段：循环处理阶段---------------*///3.循环处理栈的中的元素直至栈为空while (!STKEmpty(&stk)){//4.弹出当前处理区间的左右边界int begin = STKTop(&stk);STKPop(&stk);int end = STKTop(&stk);STKPop(&stk);//5.选择任意的分区算法对当前的区间进行分区int key = PartSort3(a, begin, end);//6.将存在的区间压入栈中//6.1：先将右子区间[key+1, end]入栈（如果存在的话）if (key + 1 < end){STKPush(&stk, end);STKPush(&stk, key + 1);}//6.2:再将左子区间[left,key-1]入栈（如果存在的话）if (begin < key - 1){STKPush(&stk, key - 1);STKPush(&stk, begin);}}/*---------------第三阶段：释放资源阶段---------------*/STKDestroy(&stk);}

注：快速排序的非递归实现使用了其他的辅助数据结构：

1. 辅助栈

快速排序的属性怎么样？

关于快速排序属性的大总结：

属性 描述 时间复杂度 最坏： O ( n 2 ) O(n^2) O(n2)（若基准每次选到极值，如：完全逆序数组）
平均：$O(nlogn)$（分治优化后） 空间复杂度 $O(logn)$（递归栈空间，平均情况）
$O(n)$（最坏情况，需优化基准选择） 稳定性 不稳定排序 适用场景 大规模数据排序、
内存排序（不适用于链表，更适合数组）

---------------归并排序---------------

---------------归并排序---------------

归并排序是什么？

归并排序（Merge Sort）：是一种基于分治思想（Divide and Conquer） 的排序算法。

• 它的核心思想是：将数组不断分割成子数组，直到子数组长度为 1（有序），然后将有序的子数组合并，最终得到完整有序数组。

归并排序的思想是什么？

归并排序的基本思想：

1. 分解（Divide）：
   • 将待排序数组从中间划分为左右两个子数组，递归地对每个子数组重复分解操作，直到子数组长度为 1（单个元素默认有序）
2. 合并（Merge）：
   • 将两个有序的子数组合并成一个新的有序数组。合并过程中，通过双指针遍历两个子数组，逐个比较元素大小，按顺序放入临时数组，最终将临时数组复制回原数组对应位置。
3. 终止条件：
   • 当子数组长度为 1 时，停止分解，开始向上合并有序子数组，直至整个数组有序。

归并排序怎么使用代码实现？

归并排序递归实现

//主函数：MergeSort()函数是入口，函数内部是一些可重复的代码//子函数：_MergeSort()函数是归并排序的核心void _MergeSort(int* a, int* tmp, int begin, int end){//1.处理特殊的情况：“区间中没有元素 + 区间中只有一个元素” （递归结束条件）if (begin >= end) return;//2.计算区间的中间点：（防溢出写法：begin + (end - begin)/2）int mid = begin + end >> 1; //装逼写法（不建议使用，请勿装逼）//3.递归处理左右子区间//3.1：递归处理左子区间_MergeSort(a, tmp, begin, mid);//3.2：递归处理右子区间_MergeSort(a, tmp, mid + 1, end);//4.定义左右子数组的边界 + 临时数组的写入位置int begin1 = begin, end1 = mid; //左子数组的边界int begin2 = mid + 1, end2 = end; //右子数组的边界int pos = begin;//5.双指针法合并：选择较小的元素优先放入while (begin1 <= end1 && begin2 <= end2) //只要有一个子数组归并完毕循环就结束 ---> 两个数组都未完成归并while循环继续进行{if (a[begin1] <= a[begin2]) //稳定排序的关键：相等时取前一个元素{tmp[pos++] = a[begin1++];}elsetmp[pos++] = a[begin2++];}//6.处理左右子数组剩余的元素//6.1：处理左数组中的剩余的元素（如果有的话）while (begin1 <= end1){tmp[pos++] = a[begin1++];}//6.2：处理右数组中的剩余的元素（如果有的话）while (begin2 <= end2){tmp[pos++] = a[begin2++];}//7.将合并结果从tmp数组拷贝回原数组的对应的区间memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));// 注意：只拷贝当前处理的范围[begin, end]}/*----------------------------归并主函数（递归实现）----------------------------*/void MergeSort(int* a, int n){/*-----------------第一阶段：动态创建临时数组-----------------*/int* tmp = (int*)malloc(n * sizeof(int));if (tmp == NULL){perror(\"malloc fail\");return;}/*-----------------第二阶段：调用核心排序函数-----------------*/_MergeSort(a, tmp, 0, n - 1);//处理整个数组[0, n-1]/*-----------------第三阶段：释放临时数组内存-----------------*/free(tmp);tmp = NULL;}

归并排序的非递归实现

/*----------------------------归并排序（非递归实现）----------------------------*///递归虽好，但是存在栈溢出的风险，所以我们还是有必要学习一下归并排序的非递归实现的//说明：之前我们为实现快速排序的非递归使用的栈，但是归并的非递归不能简单的借助栈就能实现//原因：快排的非递归类似二叉树的前序遍历，而递归类似于后序遍历，在递归过程中要先保存结果，在回溯阶段再进行归并void MergeSortNonR(int* a, int n){//1.动态创建临时数组int* tmp = (int*)malloc(n * sizeof(int));if (tmp == NULL){perror(\"malloc fail\");return;}//2.定义一个变量记录归并子数组的大小int gap = 1; //从1开始，单个元素视为已排序//3.使用while循环进行循环归并while (gap < n) //当子数组的大小 >= 原数组的长度时归并结束 ---> 反面即是while循环的条件{//4.遍历整个区间，每次处理两个相邻的gap大小的区间for (int i = 0; i < n; i += 2 * gap){/*--------------------第一步：确定两个待递归区间的边界--------------------*/int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;/*--------------------第二步：修正边界防止数组越界--------------------*///1）情况1：第二个区间完全越界（无需归并）if (begin2 >= n){break;}//2）情况2：第二个区间部分越界（修正end2）if (end2 >= n){end2 = n - 1;}/*--------------------第三步：归并两个有序区间--------------------*///1.定义临时数组的写入位置int pos = i;//2.双指针法合并两个区间while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]) //稳定排序的关键：相等时取前一个元素{tmp[pos++] = a[begin1++];}else{tmp[pos++] = a[begin2++];}}//3.处理左右子数组剩余的元素//3.1：处理左数组中的剩余的元素（如果有的话）while (begin1 <= end1){tmp[pos++] = a[begin1++];}//3.2：处理右数组中的剩余的元素（如果有的话）while (begin2 <= end2){tmp[pos++] = a[begin2++];}//4.将归并结果拷贝回原数组（仅拷贝当前处理的范围）memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));}//5.扩大归并区间的大小gap *= 2;}//6.释放资源free(tmp);tmp = NULL;}

归并排序的属性怎么样？

关于归并排序属性的大总结：

属性 描述 时间复杂度 始终为 $O(nlogn)$（分解和合并均需线性时间，递归深度为 $logn$ 空间复杂度 $O(n)$（合并时需要临时数组存储元素，递归栈空间为 $O(\log n)$ 稳定性 稳定排序 适用场景 大规模数据排序
外排序（可处理磁盘等外部存储数据）
链表排序（无需随机访问）

---------------计数排序---------------

计数排序是什么？

计数排序（Counting Sort）：是一种非比较排序算法，通过统计元素出现的次数来实现排序。

计数排序的思想是什么？

在了解计数排序的思想之前，我们需要先明确计数排序存在两种实现方式，分别是 简单实现 和 完整实现

这里我们着重学习简单实现，当然下面我们也会给出完整实现的基本思想，但是我们不会再使用代码实现了

简单实现的基本思想

计数排序简单实现的基本思想：

计数排序简单实现怎么使用代码实现？

void CountSort(int* a, int n){/*---------------第一阶段：确定数据的范围---------------*///1.使用假设法：先定义两个变量记作是数据中的最小/最大值int minn = a[0], maxx = a[0];//2.遍历数组寻找数组中的最大值和最小值for (int i = 0; i < n; i++){//2.1：修正最小值if (a[i] < minn){minn = a[i];}//2.2：修正最大值if (a[i] > maxx){maxx = a[i];}}//3.计算实际数据的范围int range = maxx - minn + 1;/*---------------第二阶段：创建计数的数组---------------*/int* count = (int*)calloc(range, sizeof(int));if (count == NULL){perror(\"calloc fail\");return;}/*---------------第三阶段：统计元素出现次数---------------*/for (int i = 0; i < n; i++) //遍历原数组[0,n]的区间中的元素{count[a[i] - minn]++; //将数据映射到count数组[0,range-1]区间中}/*---------------第四阶段：重构待排序数组---------------*///1.定义元素数组的写入位置int pos = 0;//2.使用for循环遍历count数组for (int i = 0; i < range; i++){//2.1：将count数组中元素转化为：元素的数量while (count[i]--){//2.2：将count数组的索引转化回：原始的值a[pos++] = i + minn;}}/*---------------第五阶段：释放资源---------------*/free(count);count = NULL;}

完整实现的基本思想

计数排序完整实现的基本思想：

1. 统计频率：
   • 创建一个频率数组（计数数组），记录每个元素在原数组中出现的次数
2. 计算前缀和：
   • 将频率数组转换为前缀和数组，前缀和的值表示 “小于等于当前元素的总数”，用于确定元素在排序后数组中的位置
3. 重构数组：
   • 从原数组末尾开始遍历（保证稳定性），根据前缀和数组确定每个元素的正确位置，依次放入结果数组中，并将前缀和减 1（处理重复元素）

计数排序的属性怎么样？

关于计数排序属性的大总结：

属性 描述 时间复杂度 $O(n+k)$（n 为元素个数，k 为取值范围） 空间复杂度 $O(n+k)$（计数数组和结果数组） 稳定性 稳定排序 适用场景 元素取值范围有限（如：整数、枚举值）
大规模数据且 k ≪ n 2 k \\ll n^2 k≪n2 的场景

------------------------------

八大排序的性能大总结

注意：表格中的内容无需全部记忆，可按以下要求有选择地记忆：

1. 时间复杂度：重点记忆绿色和蓝色框中的内容，明确不同排序算法在典型场景下的时间复杂度表现。
2. 易错点：特别关注红色框中的内容，这些是容易出错的关键细节，需重点理解并强化记忆。