排序

在排序过程中，每趟都能确定一个元素在其最终位置的有冒泡排序、简单选择排序、堆排序、快速排序，其中前三者能形成全局有序的子序列，后者能确定枢轴元素的最终位置。

提示

• 选择排序、基数排序，排序过程中的比较次数与序列初始状态无关。
• 直接插入、简单选择、基数排序，排序趟数与原始状态无关
• 基数排序，元素移动次数与关键字初始排序无关

排序算法可视化

Comparison Sorting Visualization

---

内部排序算法的比较

image.png

1. 若 $n$ 较小, 可采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动 次数较简单选择排序的多, 因而当记录本身信息量较大时, 用简单选择排序较好。
2. 若文件的初始状态已按关键字基本有序, 则选用直接插入或冒泡排序为宜。
3. 若 $n$ 较大, 则应采用时间复杂度为 $O\left(n \log _{2} n\right)$ 的排序方法: 快速排序、堆排序或归并排 序。快速排序被认为是目前基于比较的内部排序方法中最好的方法, 当待排序的关键 字随机分布时, 快速排序的平均时间最短。堆排序所需的辅助空间少于快速排序, 并 且不会出现快速排序可能出现的最坏情况, 这两种排序都是不稳定的。若要求排序稳 定且时间复杂度为 $O\left(n \log _{2} n\right)$, 则可选用归并排序。但本章介绍的从单个记录起进行两 两归并的排序算法并不值得提倡, 通常可以将它和直接插入排序结合在一起使用。先 利用直接插入排序求得较长的有序子文件, 然后两两归并。直接插入排序是稳定的, 因此改进后的归并排序仍是稳定的。
4. 在基于比较的排序方法中, 每次比较两个关键字的大小之后, 仅出现两种可能的转移, 因此可以用一棵二叉树来描述比较判定过程, 由此可以证明: 当文件的 $n$ 个关键字随 机分布时, 任何借助于 “比较” 的排序算法, 至少需要 $O\left(n \log _{2} n\right)$ 的时间。
5. 若 $n$ 很大, 记录的关键字位数较少且可以分解时, 采用基数排序较好。
6. 当记录本身信息量较大时, 为避免耗费大量时间移动记录, 可用链表作为存储结构。