数据结构实践项目——排序-阿里云开发者社区

开发者社区> 人工智能> 正文

数据结构实践项目——排序

简介: 本文是[数据结构基础系列(9):排序]课程的实践项目。 本文针对: 1. 排序问题及导学 2. 插入排序之直接插入排序 3. 插入排序之希尔排序 4. 交换排序之冒泡排序 5. 交换排序之快速排序 6. 选择排序之直接选择排序 7. 选择排序之堆排序 8. 归并排序 9. 简单的计数排序 10. 基数排序 11. 各种排序的比较 纸上谈兵:“

本文是[数据结构基础系列(9):排序]课程的实践项目。

本文针对:
1. 排序问题及导学
2. 插入排序之直接插入排序
3. 插入排序之希尔排序
4. 交换排序之冒泡排序
5. 交换排序之快速排序
6. 选择排序之直接选择排序
7. 选择排序之堆排序
8. 归并排序
9. 简单的计数排序
10. 基数排序
11. 各种排序的比较

纸上谈兵:“知原理”检验题目

1.给定序列{57, 40, 38, 11, 13, 34, 48, 75, 6, 19, 9, 7},采用下面的算法,分别描述排序的过程:
(1)直接插入排序; (2)希尔排序; (3)冒泡排序; (4)快速排序; (5)直接选择排序; (6)堆排序; (7)归并排序; (8)简单的计数排序; (9)基数排序
2、关于堆
(1)下列关键码序列中__是堆。
  A. (54,41,20,16,30,6,36,24,12)
  B. (54,41,20,36,12,6,16,24,30)
  C. (54,20,41,36,12,6,16,30,24)
  D. (54,30,20,24,12,16,6,41,36)
(2)已知关键字序列5,8,12,19,28,20,15,22是小根堆,插入关键字3,调整好后得到的小根堆是什么?
3、如果将所有中国人按照生日来排序,则使用(   )算法最快?
4、一个序列中有10000个元素,若只想得到其中前10个最小元素,则最好采用(   )排序方法?
5、在有n个关键字互不相同的记录中,找到关键字由小到大第k大的记录,用(   )排序的思想设计算法更好?

课后上机实践

【项目1 - 验证算法】
  用序列{57, 40, 38, 11, 13, 34, 48, 75, 6, 19, 9, 7}作为测试数据,运行并本周视频中所讲过的算法对应 程序,观察运行结果并深刻领会算法的思路和实现方法:(1)直接插入排序;(2)希尔排序;(3)冒泡排序;(4)快速排序;(5)直接选择排序;(6)堆排序;(7)归并排序;(8)基数排序。
  参考解答:(1) (2) (3) (4) (5) (6) (7) (8)

【项目2 - 大数据集上排序算法性能的体验】
  设计一个函数,产生一个至少5万条记录的数据集合。在同一数据集上,用直接插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、基数排序等算法进行排序,记录所需要的时间,经过对比,得到对复杂度不同的各种算法在运行时间方面的感性认识。

提示1:这一项目需要整合多种排序算法,可以考虑先建设排序算法库,作为我们这门课算法库的收官之作;
提示2:本项目旨在获得对于复杂度不同算法的感性认识,由于数据分布特点、计算机运行状态等不同,其结果并不能完全代替对算法复杂度的理论分析;
提示3:由于C语言标准提供的时间函数只精确到秒,几种O(nlog2n)级别的算法,在5万条记录的压力下,并不能明显地看出优劣,可以忽略直接插入排序、冒泡排序、直接选择排序这三种相对低效率的算法(以节约时间。若能够忍受他们长时间地运行,请自便),成10倍地加大数据量,然后进行观察。

参考解答

【项目3 - 归并排序算法的改进】
  采用归并排序、快速排序等高效算法进行排序,当数据元素较少时(如n≤64),经常直接使用直接插入排序算法等高复杂度的算法。这样做,会带来一定的好处,例如归并排序减少分配、回收临时存储区域的频次,快速排序减少递归层次等。
试按上面的思路,重新实现归并排序算法。
参考解答

【项目4 - 英文单词的基数排序】
  设计一个基数排序的算法,将一组英文单词,按字典顺序排列。假设单词均由小写字母或空格构成,最长的单词有MaxLen个字母。
参考解答

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章