计算机应用专业上机考试排序算法指导
以关键字序列(265,301,751,129,937,863,742,694,076,438)为例,分别写出执行以下排序算法的各趟排序结束时,关键字序列的状态。
(1) 直接插入排序 (2)希尔排序 (3)冒泡排序 (4)快速排序
(5) 直接选择排序 (6) 堆排序 (7) 归并排序 (8)基数排序
上述方法中,哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例。
答:
(1)直接插入排序:(方括号表示无序区)
初始态: 265[301 751 129 937 863 742 694 076 438]
第一趟:265 301[751 129 937 863 742 694 076 438]
第二趟:265 301 751[129 937 863 742 694 076 438]
第三趟:129 265 301 751[937 863 742 694 076 438]
第四趟:129 265 301 751 937[863 742 694 076 438]
第五趟:129 265 301 751 863 937[742 694 076 438]
第六趟:129 265 301 742 751 863 937[694 076 438]
第七趟:129 265 301 694 742 751 863 937[076 438]
第八趟:076 129 265 301 694 742 751 863 937[438]
第九趟:076 129 265 301 438 694 742 751 863 937
(2)希尔排序(增量为5,3,1)
初始态: 265 301 751 129 937 863 742 694 076 438
第一趟:265 301 694 076 438 863 742 751 129 937
第二趟:076 301 129 265 438 694 742 751 863 937
第三趟:076 129 265 301 438 694 742 751 863 937
(3)冒泡排序(方括号为无序区)
初始态 [265 301 751 129 937 863 742 694 076 438]
第一趟: 076 [265 301 751 129 937 863 742 694 438]
第二趟: 076 129 [265 301 751 438 937 863 742 694]
第三趟: 076 129 265 [301 438 694 751 937 863 742]
第四趟: 076 129 265 301 [438 694 742 751 937 863]
第五趟: 076 129 265 301 438 [694 742 751 863 937]
第六趟: 076 129 265 301 438 694 742 751 863 937
(4)快速排序:(方括号表示无序区,层表示对应的递归树的层数)
初始态: [265 301 751 129 937 863 742 694 076 438]
第二层: [076 129] 265 [751 937 863 742 694 301 438]
第三层: 076 [129] 265 [438 301 694 742] 751 [863 937]
第四层: 076 129 265 [301] 438 [694 742] 751 863 [937]
第五层: 076 129 265 301 438 694 [742] 751 863 937
第六层: 076 129 265 301 438 694 742 751 863 937
(5)直接选择排序:(方括号为无序区)
初始态 [265 301 751 129 937 863 742 694 076 438]
第一趟: 076 [301 751 129 937 863 742 694 265 438]
第二趟: 076 129 [751 301 937 863 742 694 265 438]
第三趟: 076 129 265[ 301 937 863 742 694 751 438]
第四趟: 076 129 265 301 [937 863 742 694 751 438]
第五趟: 076 129 265 301 438 [863 742 694 751 937]
第六趟: 076 129 265 301 438 694 [742 751 863 937]
第七趟: 076 129 265 301 438 694 742 [751 863 937]
第八趟: 076 129 265 301 438 694 742 751 [937 863]
第九趟: 076 129 265 301 438 694 742 751 863 937
(6)堆排序:(通过画二*树可以一步步得出排序结果)
初始态 [265 301 751 129 937 863 742 694 076 438]
建立初始堆: [937 694 863 265 438 751 742 129 075 301]
第一次排序重建堆:[863 694 751 765 438 301 742 129 075] 937
第二次排序重建堆:[751 694 742 265 438 301 075 129] 863 937
第三次排序重建堆:[742 694 301 265 438 129 075] 751 863 937
第四次排序重建堆:[694 438 301 265 075 129] 742 751 863 937
第五次排序重建堆:[438 265 301 129 075] 694 742 751 863 937
第六次排序重建堆:[301 265 075 129] 438 694 742 751 863 937
第七次排序重建堆:[265 129 075] 301 438 694 742 751 863 937
第八次排序重建堆:[129 075]265 301 438 694 742 751 863 937
第九次排序重建堆:075 129 265 301 438 694 742 751 863 937
(7)归并排序(为了表示方便,采用自底向上的归并,方括号为有序区)
初始态:[265] [301] [751] [129] [937] [863] [742] [694] [076] [438]
第一趟:[265 301] [129 751] [863 937] [694 742] [076 438]
第二趟:[129 265 301 751] [694 742 863 937] [076 438]
第三趟:[129 265 301 694 742 751 863 937] [076 438]
第四趟:[076 129 265 301 438 694 742 751 863 937]
(8)基数排序(方括号内表示一个箱子共有10个箱子,箱号从0到9)
初始态:265 301 751 129 937 863 742 694 076 438
第一趟:[] [301 751] [742] [863] [694] [265] [076] [937] [438] [129]
第二趟:[301] [] [129] [937 438] [742] [751] [863 265] [076] [] [694]
第三趟:[075] [129] [265] [301] [438] [] [694] [742 751] [863] [937]
在上面的排序方法中,直接插入排序、冒泡排序、归并排序和基数排序是稳定的,其他排序算法均是不稳定的,现举实例如下:以带*号的表示区别。
希尔排序:[8,1,10,5,6,*8]
快速排序:[2,*2,1]
直接选择排序:[2,*2,1]
堆排序:[2,*2,1]
【计算机应用专业上机考试排序算法指导】相关文章:
热点推荐:
工学
- 2020-11-17【工学】2012年自考“工程项目管理”单选练习(9)
- 2020-11-17【工学】2012年自考“互联网软件应用与开发”复习资料(1)
- 2020-11-17【工学】2012年自考“互联网软件应用与开发”复习资料(18)
- 2020-11-17【工学】2012年自考“互联网软件应用与开发”复习资料(34)
- 2020-11-17【工学】2012年自考“互联网软件应用与开发”复习资料(35)
- 2020-11-17【工学】2012年自考“互联网软件应用与开发”复习资料(38)
- 2020-11-17【工学】2012年自考“互联网软件应用与开发”复习资料(41)
- 2020-11-17【工学】2012年自考“互联网及其应用”串讲笔记(1)
其他最新资讯
- 2023-12-29【自考政策】广西自考网络助学平台新增61门课程
- 2020-12-04【免考问题】哪些证书可以免考自考相关课程?
- 2020-12-04【免考问题】自考免考有哪些条件?
- 2020-12-04【综合问题】自考本科文凭有用吗?
- 2020-12-04【综合问题】自考本科需要考多少门课?
- 2020-11-17【综合问题】江苏省高等教育自学考试网上报名常见问题及解答
- 2020-11-17【经济学】2012年自考“中国税制”笔记串讲(8)
- 2020-11-17【自考政策】全国自考办领导:未来自考将大力发展网络助学
网友关注
- 【自考报名】广西贺州2011年10月自考报名通知
- 【考务考籍】撰写毕业论文 看清时间安排
- 【自考报名】山西自考2011年10月考试日程(本科10—10)
- 【考务考籍】2014年上海外国语大学自考咨询问题集(八)
- 【考务考籍】房屋建筑工程(专科)、建筑工程(独立本科段) 实践课程考核通知
- 【考务考籍】2014年同济大学自考咨询问题集(六)
- 【考务考籍】2014年上海市自考办咨询问题集(五)
- 【考务考籍】2014年同济大学自考咨询问题集(二)
网友关注视频
- 外研版英语三起6年级下册(14版)Module3 Unit2
- 七年级英语下册 上海牛津版 Unit9
- 【部编】人教版语文七年级下册《过松源晨炊漆公店(其五)》优质课教学视频+PPT课件+教案,江苏省
- 【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案,广东省
- 二次函数求实际问题中的最值_第一课时(特等奖)(冀教版九年级下册)_T144339
- 3月2日小学二年级数学下册(数一数)
- 外研版英语三起5年级下册(14版)Module3 Unit1
- 冀教版小学数学二年级下册第二单元《有余数除法的竖式计算》