首页 > 试题广场 >

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描

[单选题]
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入的排序算法是（） 
  • 归并排序
  • 选择排序
  • 希尔排序
  • 插入排序
查看答案及解析
添加回答
唐飞dream头像 唐飞dream
归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
如　设有数列{6，202，100，301，38，8，1}
初始状态：6,202,100,301,38,8，1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
总的比较次数为：3+4+4=11,；
逆序数为14；
简单选择排序的基本思想：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。
以下为简单选择排序的存储状态，其中大括号内为无序区，大括号外为有序序列：
初始序列：{ 49 27 65 97 76 12 38 }
第1趟：12与49交换：12 { 27 65 97 76 49 38 }
第2趟：27不动　：12 27 { 65 97 76 49 38 }
第3趟：65与38交换：12 27 38 { 97 76 65 49}
第4趟：97与49交换：12 27 38 49 { 97 76 65 }
第5趟：76与65交换：12 27 38 49 65 { 97 76 }
第6趟：97与76交换：12 27 38 49 65 76 97 完成
希尔排序：
插入排序：
发表于 2016-04-15 20:00:37 回复(0)
Orange。头像 Orange。
题目说了找到位置插入了，肯定是插入排序了。。
发表于 2017-08-17 08:56:14 回复(0)
牛客657694号头像 牛客657694号
D
发表于 2016-11-14 23:29:19 回复(0)
提交观点

问题信息

排序
来自：美丽联合2017校园招...
难度：
3条回答 8901浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号