排序

排序（Sorting）是将一组数据元素按关键字递增或递减排列的过程，是计算机科学中最基础、应用最广泛的问题之一。数据库索引、搜索结果、成绩排名、快递分拣……背后都依赖高效的排序算法。

本章要解决的问题

面对不同规模、不同初始状态的数据，如何选择最合适的排序算法？稳定性、空间开销如何权衡？本章系统介绍各类内部排序与外部排序算法，帮助你在实际应用中做出正确选择。

子章节	算法类别	平均时间复杂度	稳定性
排序的起源与实际意义	概述	-	-
插入排序	插入	$O(n^2)$	稳定
冒泡排序	交换	$O(n^2)$	稳定
选择排序	选择	$O(n^2)$	不稳定
希尔排序	插入(改进)	$O(n^{1.3})$	不稳定
快速排序	交换	$O(n\log n)$	不稳定
堆排序	选择	$O(n\log n)$	不稳定
归并排序	归并	$O(n\log n)$	稳定
基数排序	非比较	$O(d(n+r))$	稳定
外部排序	外部	$O(n\log n)$	-
各种排序算法的比较	综合对比	-	-

基础路线：插入排序 → 冒泡排序 → 选择排序，掌握 $O(n^2)$ 级简单排序。

进阶路线：快速排序 → 归并排序 → 堆排序，理解分治与堆结构。

扩展路线：希尔排序 → 基数排序 → 外部排序，了解改进与非比较排序。

排序章节各小节相对独立，可结合动画演示逐个击破。学完所有算法后，务必阅读「各种排序算法的比较」进行综合复盘。