---
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]]

## 相关页面

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