title: 排序 tags:

module
data-structure-and-algorithm
sort
joplin type: module source_type: reconstructed created: 2026-04-22 updated: 2026-04-22 ---

排序

[!abstract] 这一模块处理最经典的一类算法问题。重点不是默写代码，而是比较不同排序的基本思想、复杂度、稳定性和适用输入特征。

模块结论

[[排序算法]] 可以从插入、交换、选择、归并、堆等思路分类理解。
同样是 O(n^2) 的算法，执行思路和适用场景也不同。
快速排序平均性能优秀，但最坏情况退化明显；堆排序与插入类排序则体现了不同的结构利用方式。

一、插入类排序

直接插入排序
折半插入排序
希尔排序

核心思路

把当前元素插入到前面已经基本有序的区间。
数据越接近有序，插入类排序通常表现越好。

二、交换类排序

冒泡排序
快速排序

对比重点

冒泡排序通过相邻交换逐步把大元素或小元素推到一侧。
快速排序通过划分把序列分成两部分后递归处理。

三、选择与堆思想

选择类排序的核心是每趟选出最值。
堆排序利用 [[堆]] 快速维护当前最值或最大值。

四、比较维度

时间复杂度：最好、平均、最坏。
空间复杂度：是否需要额外辅助空间。
稳定性：相等关键字相对顺序是否保留。
适用输入：近乎有序、小规模、随机分布等。

五、为什么快速排序常见

平均效率高。
原地划分，额外空间开销相对小。
工程实现优化空间大。

但也要记住

枢轴选得差时会退化。
递归深度和分区策略直接影响表现。

六、易错点

不要只记“复杂度结论”，要能解释算法为什么达到这个复杂度。
稳定性不是时间复杂度能替代的问题。
希尔排序本质上仍属于插入排序思想的改进。

七、复习提问

插入排序、冒泡排序、快速排序的核心动作分别是什么？
为什么快排平均快，但最坏情况差？
堆排序是如何利用堆结构完成排序的？
稳定性在什么场景下重要？

来源

[[raw/Joplin/计算机专业基础/数据结构与算法/(C)840数据结构与算法/8.排序.md]]
[[raw/Joplin/计算机专业基础/数据结构与算法/(C)840数据结构与算法/3.堆--以最大堆为例.md]]

相关页面

[[数据结构与算法]]
[[排序算法]]
[[堆]]