排序的起源与实际意义
排序（Sorting）是人类最早面对的数学与计算问题之一。无论是古代的账本、名册，还是现代的数据库、搜索引擎，排序都无处不在。
历史故事
-
古代账本与名册：
- 在古埃及、巴比伦等文明，官员需要将大量物品、人口、税收等信息进行有序排列，方便查找和管理。
- 中国古代科举考试、官员升迁也需对考生、官员进行排序。
-
图书馆与字典：
- 图书馆管理员需将书籍按编号、作者、主题等排序，便于借阅。
- 字典、词典的编纂离不开字母顺序、拼音顺序等排序规则。
-
现代应用：
- 互联网搜索结果、商品推荐、成绩排名、快递分拣等，背后都依赖高效的排序算法。
排序的基本概念
- 排序：将一组数据元素按关键字递增或递减排列的过程
- 关键字：排序所依据的字段，可以是主关键字（唯一）或次关键字
排序的分类
- 按存储介质：内部排序（数据全部在内存，本章重点）与外部排序（数据量大，需借助外存）
- 按比较方式：比较排序（通过比较关键字大小决定次序）与非比较排序（基数、计数、桶排序，不比较关键字）
稳定性
稳定排序：若两个相等元素排序前后的相对位置不变，则称该排序算法是稳定的。稳定性在多关键字排序（如先按总分、再按语文分）中非常重要。
评价指标
- 时间复杂度：最好、最坏、平均情况下的比较/移动次数
- 空间复杂度：排序所需的辅助空间
- 稳定性：相等元素的相对位置是否保持
- 算法实现的简单程度：常数因子、代码复杂度
排序的现实意义
- 提高查找效率：有序数据便于二分查找、范围查询等高效操作。
- 数据分析与展示：排序后数据更易于分析、对比和可视化。
- 系统优化：许多算法（如归并、去重、聚类等）都以排序为基础。
排序不仅是计算机科学的基础问题，也是人类社会管理和认知世界的重要工具。