2. 计算机
  3. 下列排序方法中，最坏情况下比较次数最少的是______。

下列排序方法中，最坏情况下比较次数最少的是______。

admin2009-09-28  68
问题 下列排序方法中，最坏情况下比较次数最少的是______。
选项 A、冒泡排序
B、简单选择排序
C、直接插入排序
D、堆排序
答案D
解析 (1)冒泡排序法：是—种最简单的交换类排法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要比较的次数为n(n-1)/2次。  (2)直接插入排序法：在直接插入排序法中，每—次比较后最多移掉—个逆序，因此，选种排序方法的效率与冒泡排序法相同。在最坏情况下，直接插入排序需要n(n-1)/2次比较。  (3)简单选择排序法：对于长度为n的新台阶列。选择排序需要扫描n-1遍，每—遍扫描均从剩下的子表中选出最小的元素，然后将该最小的元素与子表中的第—个元素进行交换。简单选择选择排序法在最坏情况下需要比较n(n-1)/2次。 (4)堆排序法：堆排序的方法为：①首先将—个无序序列建成。②然后将堆顶元素(序列中的最大项)与堆中最后—个元素交换(最大项应该在序列的最后)。在最坏情况下，堆排序需要比较的次数为O(nlog2n)。假设线性表的长度为16，那么冒泡排序、直接插入排序、简单选择排序都需要比较120次，而堆排序需要比较64次。
转载请注明原文地址:https://www.kaotiyun.com/show/z2Wp777K
本试题收录于： 二级C语言题库NCRE全国计算机二级分类
0

二级C语言

NCRE全国计算机二级

相关试题推荐
随机试题
最新回复(0)