排序算法对比

2026/9/19大约 6 分钟

1. 考点：常见排序算法的对比

类别	排序方法	平均情况时间复杂度	特殊情况时间复杂度	空间复杂度（辅助存储）	稳定性
插入排序	直接插入	O(n²)	基本有序最优 O(n)	O(1)	稳定
插入排序	Shell 排序	O(n^1.3)	—	O(1)	不稳定
选择排序	直接选择	O(n²)	—	O(1)	不稳定
选择排序	堆排序	O(n log₂ n)	—	O(1)	不稳定
交换排序	冒泡排序	O(n²)	基本有序最优 O(n)	O(1)	稳定
交换排序	快速排序	O(n log₂ n)	基本有序最差 O(n²)	O(1)	不稳定
归并排序		O(n log₂ n)	—	O(n)	稳定
基数排序		O(d(n + rd))	—	O(rd)	稳定

时间复杂度速记：
- 平方阶 $O(n^2)$ ：直接插入、直接选择、冒泡排序。
- 线性对数阶 $O(n\log_2 n)$ ：堆排序、快速排序、归并排序。
- 特殊：Shell排序约为 $O(n^{1.3})$ ，基数排序为 $O(d(n+rd))$ 。
稳定性口诀：
- 稳定的排序有：插入、冒泡、归并、基数（可记为：“情（琴）人（插入）冒（冒泡）泡（归并、基数...音译结合）”或独立记忆）。
- 不稳定的排序有：Shell排序、直接选择、堆排序、快速排序。

在选取排序方法时需要考虑的因素有待排序的记录个数 $n$ 、记录本身的大小、关键字的分布情况、对排序稳定性的要求、语言工具的条件和辅助空间的大小。依据这些因素，可以得到以下几点结论：

若待排序列的记录数目 $n$ 较小：可采用直接插入排序、选择排序、冒泡排序。
若待排记录按关键字基本有序：宜采用直接插入排序。
当 $n$ 很大且关键字位数较少时：采用基数排序较好。
若 $n$ 很大：则应采用时间复杂度为 $O(n\log_2 n)$ 的排序方法，例如快速排序、堆排序或归并排序：
1. 快速排序目前被认为是内部排序中最好的方法，当待排序的关键字为随机分布时，快速排序的平均运行时间最短。
2. 堆排序只需要一个辅助空间，并且不会出现在快速排序中可能出现的最坏情况。
3. 快速排序和堆排序都是不稳定的排序方法，若要求排序稳定，可选择归并排序。

场景驱动选择：没有绝对完美的排序算法，应根据数据规模（ $n$ 的大小）、初始状态（是否基本有序）、空间限制以及稳定性需求来综合权衡选择最合适的排序策略。

题目： 对于一个初始无序的关键字序列，在下面的排序方法中，（ C ）第一趟排序结束后，一定能将序列中的某个元素在最终有序序列中的位置确定下来。
①直接插入排序
②冒泡排序
③简单选择排序
④堆排序
⑤快速排序
⑥归并排序
A、①②③⑥
B、①②③⑤⑥
C、②③④⑤
D、③④⑤⑥

【解析】

逐一对各排序算法在第一趟排序结束后的表现进行分析：

① 直接插入排序：第一趟是将第2个元素插入到前面已排序的子序列中，此时前两个元素相对有序，但不能确定它们在最终全局有序序列中的位置。
② 冒泡排序：第一趟通过相邻元素的比较与交换，会将整个序列中最大（或最小）的元素“冒泡”移动到最右侧（或最左侧）的最终归位处，因此能够确定一个元素的位置。
③ 简单选择排序：第一趟通过在所有记录中选出最小（或最大）的记录，并将其与第一个位置的记录交换，该最值元素已经到达最终排序位置，因此能够确定一个元素的位置。
④ 堆排序：第一趟建堆完成后，将堆顶的最大（或最小）元素与末尾元素交换，此时末尾元素已经处于最终有序序列的正确位置上，因此能够确定一个元素的位置。
⑤ 快速排序：第一趟通过划分（Partition）操作，选出一个基准元素（Pivot）并将其放置到了最终正确的分隔位置上，因此能够确定该基准元素的位置。
⑥ 归并排序：第一趟是将相邻长度为1的子序列两两归并成长度为2的有序子表，元素只是在局部有序，不能确定其在全局最终序列中的位置。

综上所述，第一趟排序结束后能确定一个元素最终位置的有：②冒泡排序、③简单选择排序、④堆排序、⑤快速排序。

正确选项：C（②③④⑤）。