（嵌入式八股）第9章 嵌入式常考手撕题(三)：排序算法总结！

除了嵌入式基础相关题目和力扣相关题目，排序算法也是嵌入式面试经常考察的重点，本篇对排序算法进行了总结！

9.29 排序算法——冒泡排序（Bubble Sort）

核心思想

冒泡排序 是一种简单但高效的排序算法。它的基本思想是：

代码实现

时间复杂度分析

• 最坏情况（数组逆序）： 需要进行 n-1 轮遍历，每轮都交换元素，复杂度为 O(n²)。
• 最优情况（数组已排序）： 由于 swapped 机制，若第一轮遍历无交换，则直接终止，复杂度为 O(n)。
• 平均情况： 大约进行 O(n²) 次比较，时间复杂度仍然是 O(n²)。

总结

• 优点： 实现简单、容易理解；对于小规模数据排序表现尚可。
• 缺点： 由于大量元素交换，效率较低，尤其是对于大规模数据，冒泡排序不如 快速排序（Quick Sort） 或 归并排序（Merge Sort） 高效。

9.30 排序算法——选择排序（Selection Sort）

核心思想

选择排序（Selection Sort） 是一种简单直观的排序算法。其基本思想是：

1. 在未排序的部分中找到最小（或最大）的元素，将其放到已排序部分的末尾。
2. 继续在剩余的未排序部分中寻找最小（或最大）元素，重复以上过程，直到整个数组排序完成。

代码实现

选择排序（selectionSort 函数）

• 遍历数组，找到未排序部分的最小元素索引 minIndex。
• 交换 arr[i] 和 arr[minIndex]，将最小元素放到正确位置。

打印数组（printArray 函数）

• 遍历数组并输出排序前后的内容。

时间复杂度分析

• 最坏情况（逆序）：O(n²)
• 最优情况（已排序）：O(n²)（选择排序始终需要 O(n²) 次比较）
• 平均情况：O(n²)
• 空间复杂度：O(1)（原地排序，无需额外存储）

总结

✅ 稳定性：选择排序是不稳定的排序算法，因为相同元素可能会被交换位置。

✅ 适用场景：适用于数据量较小的情况，不适用于大规模数据排序。

✅ 优缺点：

• 优点：概念简单，适合教学；数据量小时表现尚可。
• 缺点：性能较低，与 冒泡排序（Bubble Sort） 类似，时间复杂度为 O(n²)。

9.3 1排序算法——插入排序

核心思想

插入排序（Insertion Sort） 是一种简单直观的排序算法，类似于打扑克牌时整理手牌的方式。基本步骤如下：

1. 取第一个元素作为已排序序列。
2. 从第二个元素开始，依次取出每个元素，将其插入到已排序序列的正确位置。
3. 通过从后往前扫描已排序序列，找到合适的位置进行插入。
4. 重复以上步骤，直到所有元素排序完成。

代码实现

插入排序（insertionSort 函数）

• 遍历数组，从索引 1 开始（因为索引 0 的元素可以视为已排序）。
• 用 temp 存储当前要插入的元素，并从已排序部分（j = i-1）从后往前比较：
• 如果当前元素 arr[j] 大于 temp，则将其向右移动。
• 直到找到 temp 应该插入的位置，将其插入。
• 继续下一轮，直到所有元素排序完成。

时间复杂度分析

总结

✅ 稳定性：插入排序是稳定的排序算法，不会改变相同元素的相对顺序。

✅ 适用场景：适用于数据量小，且数据大部分已排序的情况。

✅ 优缺点：

• 优点：简单易懂，适用于小规模数据排序；当数据基本有序时，性能接近 O(n)。
• 缺点：对于大规模数据，性能较差，时间复杂度为 O(n²)。

9.32 排序算法——希尔排序

核心思想

希尔排序（Shell Sort） 是 插入排序（Insertion Sort） 的优化版本。它通过引入 “增量” 来改进插入排序的性能，从而减少数据移动的次数，提升效率。

1. 选择一个 增量序列（通常从 n/2 开始，每次减半）。
2. 根据增量 gap，将数组划分为多个子序列，分别进行 插入排序。
3. 逐步缩小增量 gap，重复上述步骤，直到 gap == 1，最终完成排序。

代码实现

希尔排序（shellSort 函数）

• 选择 gap = n/2 作为初始增量，每次缩小 gap（gap /= 2）。
• 使用 插入排序 处理当前 gap 间隔的子序列。
• 继续缩小 gap，直到 gap == 1，完成排序。

核心优化点

• 减少数据移动次数：相比插入排序，希尔排序能减少较大元素的移动距离，加速排序过程。
• 适用于大规模数据排序，比普通插入排序快。

时间复杂度分析

总结

✅ 不稳定排序（相同元素的相对顺序可能会改变）。

✅ 适用于大规模数据排序，比插入排序更高效。

✅ 优缺点：

• 优点：比插入排序更快，适用于中等规模数据排序。
• 缺点：性能依赖于 增量序列（gap） 的选择，最优解不固定。

9.33 排序算法——快速排序

核心思想

快速排序（Quick Sort） 是一种 分治算法，它通过选择一个基准（pivot）将数组分成两部分，递归地对两部分进行排序，最终完成整个排序过程。

代码实现

分区（partition 函数）

• 选取 最左侧元素 作为基准 pivot。
• 左右指针扫描：high 先走，寻找比 pivot 小的元素；low 再走，寻找比 pivot 大的元素，进行交换。
• 最终 pivot 归位，左侧全是 小于 pivot 的数，右侧全是 大于 pivot 的数。

递归排序（quickSort 函数）

• 递归调用 左部分 和 右部分 继续排序，直到数组被完全排序。

时间复杂度分析

总结

✅ 不稳定排序（相同元素的相对顺序可能会改变）。

✅ 适用于大规模数据，性能优于 O(n²) 的排序方法。

✅ 优缺点：

• 优点：快速排序通常比 冒泡排序、选择排序、插入排序 快。
• 缺点：最坏情况下可能会退化成 O(n²)（若选取不良基准）。
• 优化方式：可以使用 随机选取 pivot 或 三数取中法 作为优化策略。

在实际应用中，快速排序 是 最快 的基于比较的排序之一，广泛用于数据处理。

9.34 排序算法——归并排序

核心思想