数据结构精讲 | 第九篇考研408排序算法专项练习（一）

前面几篇文章介绍的是排序算法，现在让我们开始排序算法的专项练习。

目录

• 判断题：
  • 选择题：
  • 填空题：
  1. 直接插入排序法
  2. 次优选择排序
  3. 冒泡式交换排序
  4. 快速确定第K个最大元素

判断题

1.希尔排序是稳定的算法。（错）
解析：稳定性是指如果两个元素在排序前后的相对顺序保持不变，那么这个排序算法就是稳定的。对于具有相同关键字的元素，排序后它们的相对位置应该保持不变。

2.仅基于比较的算法能得到的最好的“最坏时间复杂度”是O(NlogN)。（对）

3.对N个记录进行归并排序，归并趟数的数量级是O(NlogN)。（错）
答案：O(logN)

4. 采用冒泡算法来对N个不同的数据进行降序排列（即从大到小）。当初始序列已接近有序时所需交换次数将最多。（错误）
   解析：在初始序列已接近有序的情况下（即元素基本有序），使用冒泡排序算法的时间复杂度会较低（即运行效率较