第1篇：排序的意义与度量

为什么从排序开始

从书架上的图书排列，到购物网站的销量排行，再到搜索引擎的结果展示，排序无处不在。

排序之所以成为几乎所有算法教材和课程的开篇重点，是因为它不仅问题直观、易于理解，适合作为算法学习的入门内容，还涵盖了分治、贪心等多种基础的算法思想，有助于初学者掌握算法设计的基本范式；同时，不同排序算法在时间与空间效率上的差异，为理解算法性能分析提供了典型实例；此外，排序算法作为许多高级算法（如搜索、图算法）的基础，具有广泛应用和重要地位，是构建算法知识体系的理想起点。

为什么要学排序算法

排序的价值不仅体现在 “让数据有序” ，更体现在它所蕴含的思想：

1. 算法学习的基础 排序算法包含了几乎所有经典的算法思想：分治（归并、快排）、递归（快排），以及数据结构（堆排序），甚至一些数学思维（计数、基数排序）。通过学习排序，可以快速掌握算法分析和设计的核心理念。
2. 工程应用的基础 操作系统中，磁盘调度、内存管理都需要排序。数据库查询常常需要对结果进行排序。很多编程语言的标准库函数，例如Java的Arrays.sort，C++的std::sort，背后都隐藏着针对不同场景的优化版排序算法。
3. 思维训练的基础 学习排序，不仅是学算法本身，更是学习如何在不同场景下做取舍。例如：

• 追求稳定性还是空间效率？
• 更在意平均性能还是最坏情况？ 这些问题本质上就是工程师的思维训练。

学习前的准备工作

算法复杂度

数据规模与分布

公式示例1

$$I = \int_0^{2\pi} \sin(x)\,dx$$

公式示例2

Let $f\colon[a,b]\to\R$ be Riemann integrable. Let $F\colon[a,b]\to\R$ be $F(x)=\int_{a}^{x} f(t)\,dt$. Then $F$ is continuous, and at all $x$ such that $f$ is continuous at $x$, $F$ is differentiable at $x$ with $F'(x)=f(x)$.