计算机软考中级 知识点记忆——排序算法 冒泡排序-插入排序- 归并排序等 各种排序算法知识点整理

一、📌 分类与比较

排序算法	最优时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性	应用场景与特点	算法策略
冒泡排序	O(n)	O(n²)	O(n²)	O(1)	稳定	简单易实现，适用于小规模数据排序。	交换排序策略
插入排序	O(n)	O(n²)	O(n²)	O(1)	稳定	数据量小或基本有序时高效。	关键字：基本有序
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定	简单但效率低，适用于小规模数据。
快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)	不稳定	最常用的排序算法，适用于大规模数据。	分治法 关键字：有序或者逆序
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定	外部排序的最佳选择。	分治法
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定	适用于堆结构、优先队列的实现。
希尔排序	O(n log n)~O(n²)	O(n log n)	O(n²)	O(1)	不稳定	改进的插入排序，适用于中规模数据。
基数排序	O(d(n + k))	O(d(n + k))	O(d(n + k))	O(n + k)	稳定	适用于整数排序、字符串排序。
计数排序	O(n + k)	O(n + k)	O(n + k)	O(n + k)	稳定	适用于范围较小的整数排序。
桶排序	O(n)	O(n)	O(n²)	O(n + k)	稳定	适用于均匀分布的数据。

---

📌 1. 基本排序算法（简单易实现）

• 冒泡排序、插入排序、选择排序
• 时间复杂度高，但易于实现和理解。
• 常用于小规模数据或已基本有序的场景。
• 平均时间和最坏时间T复杂度为：O(n^2)
• 最好的时间T复杂度为：O(n) 选择最好依旧是O(n^2)
• 也就是在基本排序算法中选择的时间不管好坏都是O(n^2)

---

📌 2. 高效排序算法（分治思想、树结构）

• 快速排序、归并排序、堆排序、希尔排序
• 基于分治思想（快速排序、归并排序）或堆结构（堆排序）。
• 适用于大规模数据排序。
• 平均时间T复杂度为：O(n log n)
• 最坏时间T复杂度为：快速、希尔是O(n^2) ，其余不变
• 最好时间T复杂度为：O(n log n) 和平均一样，除了希尔是O(n log n) ~O(n^2)

---

📌 3. 非比较排序算法（适用于特定场景）

• 基数排序、计数排序、桶排序
• 不依赖于比较操作，适用于整数或特定场景的数据排序。
• 时间复杂度与输入数据特性有关。

---

单独的记忆点 空间复杂度：

高级排序的快速排序空间复杂度是：O(log n)

高级排序的归并排序和非比较排序算法的空间复杂度是：O(n)

其余的都是O(1) 原地排序

空间复杂度越大，说明使用的额外空间更多。

---

📌 4. 常考点与总结

📚 软考中常考内容：

1. 各种排序算法的 时间复杂度、空间复杂度、稳定性分析。
2. 适用场景：如什么时候选择快速排序、什么时候使用归并排序。
3. 基于 分治思想（快速排序、归并排序）与堆结构（堆排序） 的应用。
4. 非比较排序的特点与应用（基数排序、计数排序、桶排序）。

💡 记忆技巧：

• 稳定性：一般来说，非比较排序和插入、冒泡、归并是稳定的。（非比较排序 + 茶树泡饼）树：基数排序
• 时间复杂度 O(n log n)：快速排序、归并排序、堆排序。
• 非比较排序：计数、基数、桶排序特别适用于整数或特定场景。

效率排序来看：

• O(1) > O(log n) > O(n) > O(n log n) > O(n²) > O(2ⁿ) > O(n!)
• 你的理解非常准确！我们通常把 O(n log n) 算法称为 “高级排序算法”，而把 O(n²) 算法称为 “基础排序算法”。

---

二、时间复杂度的描述，自简单到复杂

1. O(1) - 常数时间复杂度。无论输入多大，执行时间都是固定的。

2. O(log n) - 对数时间复杂度。随着输入规模的增大，所需时间按对数级别增长。

3. O(n) - 线性时间复杂度。执行时间直接与输入规模成正比。

4. O(n^2) - 平方时间复杂度。执行时间为输入规模的平方。

5. O(2^n) - 指数时间复杂度。随着输入规模的增大，所需时间呈指数级增长。

6. O(n!) - 阶乘时间复杂度。这是非常高的一种复杂度形式，不适用于大多数实际应用场景。