2. 从业资格
  3. 采用插入排序算法对n个整数排序，其基本思想是：在插入第i个整数时，前i-1个整数

采用插入排序算法对n个整数排序，其基本思想是：在插入第i个整数时，前i-1个整数

练习题库2022-08-02  57
问题 采用插入排序算法对n个整数排序，其基本思想是：在插入第i个整数时，前i-1个整数已经排好序，将第i个整数依次和第i-1, i-2, …个整数进行比较，找到应该插入的位置。现采用插入排序算法对6个整数{5.2.4.6.1.3}进行从小到大排序，则需要进行（　　）次整数之间的比较。对于该排序算法，输入数据具有（　　）特点时，对整数进行从小到大排序，所需的比较次数最多。问题1选项A.9B.10C.12D.13问题2选项A.从小到大B.从大到小C.所有元素相同D.随机分布
选项
答案 CB
解析 一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
⒈ 从第一个元素开始，该元素可以认为已经被排序
⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2~5
对于本题：{5.2.4.6.1.3}
第一趟：第一次比较，5大于2（新元素），元素5向后位移一位，而5之前无数据，即将2插入到1位，2，5
第二趟：第一次比较，5大于4（新元素），元素5向后移一位，再进行第二次比较，2小于4（新元素），即将4插入2之后的一位，即 2，4，5
依次类推…
所以比较的次数为1+2+1+4+4=12
如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n（n-1）/2次。插入排序的赋值操作是比较操作的次数加上 （n-1）次。平均来说插入排序算法的时间复杂度为O（n^2）。
转载请注明原文地址:https://tihaiku.com/congyezige/2417919.html
本试题收录于： 中级 软件评测师题库软件水平考试初中高级分类

中级 软件评测师

软件水平考试初中高级

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