2. 计算机
  3. 对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-1)/2的排序方法是( )。

对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-1)/2的排序方法是( )。

admin2011-06-13  84
问题 对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-1)/2的排序方法是(       )。
选项 A、快速排序
B、冒泡排序
C、直接插入排序
D、堆排序
答案D
解析 冒泡排序是一种最简单的交换类排序．它通过相邻元素的交换逐步将线性表变成有序。对于长度为n的线性表，在最坏的情况下，所有的元素正好为逆序，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要比较的次数为(n-1)+(n-2)+…+2+1=n(n-1)/2。快速排序也是一种互换类的排序方法，但比冒泡法的速度快，快速排序法的关键是对线性表的分割，以及对其分割出的子表再进行分割。直接插入排序是将无序列表中的各元素一次插入到已经有序的线性表中，这种排序方法的效率与冒泡排序法相同，最坏的情况下，所有元素正好为逆序，需要比较的次数为1+2+…+(n-1)+(n-2)=n(n-1)/2。堆排序属于选择类排序方法，它首先将一个无序序列建成堆，然后将堆顶元素与堆中最后一个元素交换．然后将左右子树调整为堆，继续交换元素，直至子序列为空。在最坏的情况下，堆排序需要比较的次数为()(nlog2n)。
转载请注明原文地址:https://www.kaotiyun.com/show/qVPp777K
本试题收录于： 二级C语言题库NCRE全国计算机二级分类
0

二级C语言

NCRE全国计算机二级

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