数据结构之内部排序

内部排序算法的比较

在考研中，排序算法的比较是重要内容。通常通过以下三个因素进行对比：

时空复杂度
算法的稳定性
算法的过程特征

1. 时间复杂度

时间复杂度衡量的是算法运行所需的时间，常用三种情况进行比较：最好情况、平均情况和最坏情况。

直接插入排序：
- 最好情况：$ O(n) $（当输入序列是有序的）
- 平均情况：$ O(n^2) $
- 最坏情况：$ O(n^2) $（当输入序列是逆序的）
冒泡排序：
- 最好情况：$ O(n) $（输入序列已经有序时，只需一趟扫描）
- 平均情况：$ O(n^2) $
- 最坏情况：$ O(n^2) $（输入序列完全逆序）
简单选择排序：
- 最好情况、平均情况、最坏情况：$ O(n^2) $
  （选择排序的时间复杂度与输入序列的初始状态无关）
希尔排序：
- 最好情况、平均情况：取决于增量序列，未得出确切的渐近时间复杂度。
- 最坏情况：$ O(n^{1.5}) $（增量序列为 $ n / 2, n / 4, ..., 1 $ 时）
快速排序：
- 最好情况：$ O(n n) $（每次划分恰好对半）
- 平均情况：$ O(n n) $
- 最坏情况：$ O(n^2) $（每次划分极端不均匀，退化为冒泡排序）
堆排序：
- 最好情况、平均情况、最坏情况：$ O(n n) $
2 路归并排序：
- 最好情况、平均情况、最坏情况：$ O(n n) $
基数排序：
- 最好情况、平均情况、最坏情况：$ O(d(n + r)) $
  其中 $ d $ 是关键字的位数，$ r $ 是关键字的基数。

2. 空间复杂度

空间复杂度衡量的是算法运行时所需的额外空间。

直接插入排序、冒泡排序、简单选择排序、希尔排序、堆排序：
- 空间复杂度：$ O(1) $（只需常数个辅助空间）
快速排序：
- 空间复杂度：$ O(n) $（递归栈的大小）
- 最坏情况：$ O(n) $（递归深度最大）
2 路归并排序：
- 空间复杂度：$ O(n) $（合并时需要辅助数组）
基数排序：
- 空间复杂度：$ O(n) $（需要为每一趟排序准备计数器）

3. 算法的稳定性

稳定性指的是排序过程中，相等的元素在排序后相对位置不变。

稳定的排序算法：
- 直接插入排序、冒泡排序、2 路归并排序、基数排序
不稳定的排序算法：
- 简单选择排序、快速排序、希尔排序、堆排序

4. 算法的过程特征

冒泡排序：
- 每趟处理后会把当前未排序部分中的最大值移到最后，逐步有序。
堆排序：
- 每次调整堆后，最大值或最小值会位于堆顶，逐步有序。
快速排序：
- 一趟处理后确定一个元素的最终位置，递归处理左右子数组。
归并排序：
- 将序列分成两部分，分别排序后合并，最终将所有部分合并为有序序列。

5. 表 8.1 排序算法的性质比较

算法种类	最好情况	平均情况	最坏情况	空间复杂度	是否稳定
直接插入排序	$ O(n) $	$ O(n^2) $	$ O(n^2) $	$ O(1) $	是
冒泡排序	$ O(n) $	$ O(n^2) $	$ O(n^2) $	$ O(1) $	是
简单选择排序	$ O(n^2) $	$ O(n^2) $	$ O(n^2) $	$ O(1) $	否
希尔排序	依赖增量	依赖增量	$ O(n^{1.5}) $	$ O(1) $	否
快速排序	$ O(n n) $	$ O(n n) $	$ O(n^2) $	$ O(n) $	否
堆排序	$ O(n n) $	$ O(n n) $	$ O(n n) $	$ O(1) $	否
2 路归并排序	$ O(n n) $	$ O(n n) $	$ O(n n) $	$ O(n) $	是
基数排序	$ O(d(n + r)) $	$ O(d(n + r)) $	$ O(d(n + r)) $	$ O(n) $	是

对于小规模或近似有序的数据，直接插入排序和冒泡排序性能较好。

快速排序在实际应用中性能最佳，但需注意其最坏情况下的性能退化。

归并排序和堆排序适合大规模数据的排序，归并排序还具有稳定性优势。

基数排序适合多位关键字的排序，且时间复杂度较低，但需要额外的空间

内部排序算法的应用

内部排序算法的应用通常根据以下几个因素来决定：

1. 选取排序方法的考虑因素

排序算法的选择应综合考虑以下几点：

待排序的元素数量（n）：
- 元素数量决定了算法的性能表现。对于较小的n，简单的排序算法即可胜任；而对于较大的n，选择高效的排序算法至关重要。
元素本身信息量的大小：
- 若每个记录的信息量很大，数据移动的代价较高，此时选择移动次数较少的排序算法更合适。例如，在信息量较大的情况下，选择简单选择排序优于直接插入排序，因为后者的移动次数更多。
关键字的结构及分布情况：
- 若关键字的分布有某种特性，比如初始序列部分有序，则可以利用这一特性选择适当的算法，如直接插入排序或冒泡排序更为合适。
稳定性的要求：
- 稳定性是指如果两个元素相等，在排序后它们的相对顺序保持不变。如果算法的稳定性是要求之一，那么选择如直接插入排序、冒泡排序或归并排序等稳定的排序算法。
语言工具和存储结构：
- 不同的编程语言及其提供的工具可能影响排序算法的选择，此外，算法需要的辅助空间也很重要。例如，在辅助空间有限的情况下，堆排序优于归并排序。

2. 排序算法小结

根据不同的情况，以下是排序算法的应用建议：

当n较小时：
- 采用直接插入排序或简单选择排序是合适的选择。
- 如果记录的信息量较大，则推荐使用简单选择排序，因为它涉及的移动次数较少。
当初始状态基本有序时：
- 若初始序列已经按关键字基本有序，使用直接插入排序或冒泡排序效率较高。由于这些算法在序列近似有序的情况下能够快速完成排序，时间复杂度可达到 $O(n)$。
当n较大时：
- 应选择时间复杂度为 $O(n \log n)$ 的排序算法，例如快速排序、堆排序或归并排序。
- 快速排序通常是性能最好的排序算法，特别是在随机分布的情况下，其平均时间复杂度最短。但需要注意，快速排序在最坏情况下时间复杂度为 $O(n^2)$，且不是稳定的。
- 堆排序适用于辅助空间受限的情况，它的最坏时间复杂度始终为 $O(n \log n)$，虽然不稳定，但不会出现快速排序的最坏情况。
- 归并排序是一种稳定的排序算法，且时间复杂度始终为 $O(n \log n)$，它适合在对稳定性有要求的情况下使用。
改进归并排序：
- 直接使用两两归并的归并排序不值得提倡，通常建议结合直接插入排序来提升效率。首先使用直接插入排序得到较长的有序子序列，然后再进行两两归并。这样改进的归并排序仍然是稳定的。
基数排序的应用：
- 基数排序适用于n较大、关键字位数较少且可以分解的情况。基数排序不依赖比较操作，适合特定情况下的高效排序，特别是在有大量的整数或者固定长度的字符串时。
链表存储结构：
- 当记录的信息量很大时，频繁移动数据可能代价高昂。此时，可以使用链表来代替数组存储结构，避免大量的数据移动。链表在排序过程中只需要调整指针而不是移动记录本身，这样可以极大地提高效率。