2025年考研真题-排序

2025年考研真题-排序

     下列排序算法中，最坏情况下元素移动次数最少的是（）

     A.起泡排序     B. 直接插入排序        C. 快速排序     D.简单选择排序

答案：D

解析：

       在最坏情况下（例如数组为逆序排列），各排序算法的元素移动次数如下：

1、冒泡排序‌：每次比较相邻元素，若逆序则交换。最坏情况下需要进行约 n(n−1)22n(n−1) 次交换，每次交换涉及3次移动操作，总移动次数约为 3×n(n−1)23×2n(n−1)，数量级为 O(n2)O(n2)。

2、 ‌直接插入排序‌：每次将元素插入到已排序部分的正确位置，最坏情况下需移动大量已排序元素，总移动次数也为 O(n2)O(n2)。

3、快速排序‌：最坏情况下（如已排序数组），划分极度不平衡，需进行 nn 次划分，每次划分可能移动大量元素，总移动次数同样为 O(n2)O(n2)。

4、简单选择排序‌：每轮从未排序部分选择最小元素，与未排序部分的第一个元素交换。‌无论初始顺序如何，总共只需进行 n−1n−1 次交换‌，每次交换涉及3次移动操作，因此总移动次数为 3(n−1)3(n−1)，数量级为 O(n)O(n)。