数据序列(8,9,10,4,5,6,20,1,2)只能是下列排序算法中的( )的两趟排序后的结果。

admin2014-10-20  28

问题 数据序列(8,9,10,4,5,6,20,1,2)只能是下列排序算法中的(    )的两趟排序后的结果。

选项 A、选择排序
B、冒泡排序
C、插入排序
D、堆排序

答案C

解析 直接插入排序是一种最基本的排序算法,基本操作为:将一个记录插人到一个已经排好序的有序表中,从而得到一个新的、长度增1的有序表。一般情况下,第i趟的操作为:在含有i一1个记录的有序子序列r[1…i一1]t~A--个新记录r,变成含有i个记录的有序序列r[1…i]。设置r[0]为空值,从r[1]开始保存信息,可首先将待插入的记录r复制到r[0]中,如下所示:

可把r[0]看成是r的备份,以后从r[1]~r[i一1]查找插入位置时,可直接同r[0]比较,而且r也可被覆盖了。因为r复制到r[0]后,可认为已经空出了r。考虑从后向前比较,只要r[i一1]≤r,则r的位置不必改变,否则r[i一1]>r,则将r[i一1]移动到r处,然后再比较r[i一2]和r[0],依次等等。当最后找到一个比r[0]小的关键字时,将r[0]复制到此关键字的后面一个位置,结束。
转载请注明原文地址:https://kaotiyun.com/show/M0vR777K
0

最新回复(0)