下列排序方法中，时间性能与待排序记录的初始状态无关的是（ ）。

A. 插入排序和快速排序

B. 归并排序和快速排序

C. 选择排序和归并排序

D. 插入排序和归并排序

复杂度分析 归并排序

[tag_link]

正确答案：C

排序算法的时间性能是否与初始状态相关，取决于其时间复杂度在不同输入情况下的变化。 插入排序在最好情况下（已排序）时间复杂度为 O ( n ) ，最坏和平均为 O ( n 2 ) ，因此与初始状态有关； 快速排序的平均时间复杂度为 O ( n lo g n ) ，但最坏情况下（如已排序数组且枢轴选择不当时）会退化到 O ( n 2 ) ，也与初始状态有关。 归并排序采用分治策略，无论输入数据是否有序，其时间复杂度稳定为 O ( n lo g n ) ，与初始状态无关； 选择排序始终通过遍历未排序部分寻找最小（或最大）元素，其最好、最坏和平均时间复杂度均为 O ( n 2 ) ，因此也与初始状态无关。 选项 C 中的选择排序和归并排序均满足时间性能与初始状态无关的条件，而其他选项至少包含一种与初始状态相关的算法，故 C 为正确答案。