设待排序元素序列所有元素的关键字都相等，则下列排序方法中排序速度最慢的是（ ）。

A. 直接插入排序

B. 冒泡排序

C. 简单选择排序

D. 基数排序

复杂度分析

[tag_link]

正确答案：C

当待排序元素序列中所有关键字都相等时，序列本身已处于有序状态。 此时，不同排序算法的性能表现取决于它们在最好情况下的时间复杂度或实际执行步骤。 直接插入排序 ：在最好情况下（序列有序），只需进行 n-1 次比较，且无需移动元素，时间复杂度为 O(n)，速度很快。 冒泡排序 ：通过优化（如设置交换标志），在序列有序时，一趟扫描（n-1 次比较）后即可终止，时间复杂度也为 O(n)，效率较高。 简单选择排序 ：无论序列是否有序，都必须执行 n-1 趟选择操作，每趟需比较剩余元素以确定最小（或最大）值，比较次数恒定为约 n(n-1)/2 次，时间复杂度始终为 O(n²)，无法利用有序性加速，因此在此场景下速度最慢。 基数排序 ：其时间复杂度为 O(d*(n+k))，其中 d 为关键字位数，k 为基数。 当所有关键字相等时，分配和收集操作仍需执行，但整体仍保持线性时间复杂度，远优于 O(n²)。 综上所述，在关键字全相等的情况下，简单选择排序由于固定的二次时间复杂度，排序速度最慢。