常用排序算法课程设计报告

xxxxx《xxxxx》课程设计报告重庆科技学院课程设计任务书设计题目：常用排序算法的比较学生姓名***课程名称数据结构课程设计专业班级*****地点计算机基础自主学习中心起止时间2011.11.16-12.5设计内容及要求利用随机函数产生N个随机整数，采用多种方法对这些数进行排序，然后分析各自的所需的排序时间找出较快的排序算法。要求：1)分别采用的排序算法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序，实现这批数据的排序，并把排序后的结果保存在不同的文件中。2)统计每一种排序算法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的算法。注：在完成以上数据的同时，还能采用其它的排序算法，适当加分。设计参数测试数据要求：随机产生1000个以上的随机整数，并保存在文本文件中。排序后的数据和所需的时间也保存在各自的txt文件中。进度要求参考资料1．严蔚敏吴伟民著，数据结构，清华大学出版社，2007.32．李春葆著，数据结构教程，清华大学出版社，2005.13.RichardF.GilbergBehrouzA.Forouzan,数据结构的C++伪码实现（英文版），人民邮电出版社，2002.1其它说明１.本表应在每次实施前一周由负责教师填写二份，院系审批后交院系办备案，一份由负责教师留用。２.若填写内容较多可另纸附后。3.一题多名学生共用的，在设计内容、参数、要求等方面应有所区别。教研室主任：指导教师：2011年11月16日xxxxx《xxxxx》课程设计报告I摘要排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，其中包含冒泡排序，直接插入排序，简单选择排序，希尔排序，快速排序，堆排序等，各有其特点。对排序算法比较的分析可以遵循若干种不同的准则，通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间，例如，当键是较长的字符串时，常以键比较次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录，且记录都很大时，还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。本报告将描述如何利用随机函数产生N个随机整数，采用多种方法对这些数进行排序，然后分析各自的所需的排序时间找出较快的排序算法。关键词：排序算法数据结构随机函数xxxxx《xxxxx》课程设计报告II目录摘要................................................................................................................................I1设计内容和要求........................................................................................................11.1设计内容.........................................................................................................11.2设计要求.........................................................................................................12需求分析....................................................................................................................22.1直接插入排序...............................................................................................22.2希尔排序........................................................................................................22.3快速排序:（递归和非递归）......................................................................22.4堆排序..............................................................................................................33概要设计....................................................................................................................43.1头文件...........................................................................................................43.2ADT..............................................................................................................43.3各种操作函数：...........................................................................................43.4主函数.............................................................................................................54详细设计....................................................................................................................64.1主函数............................................................................................................64.2直接插入排序..............................................................................................74.3希尔排序......................................................................................................94.4起泡排序....................................................................................................104.5快速排序....................................................................................................114.6选择排序....................................................................................................134.7堆排序........................................................................................................154.8归并排序....................................................................................................185系统测试.................................................................................................................215.1系统操作.......................................................................................................215.2测试数据......................................................................................................236总结..........................................................................................................................26致谢..............................................................................................................................27参考文献......................................................................................................................28xxxxx《xxxxx》课程设计报告11设计内容和要求1.1设计内容利用随机函数产生N个随机整数，采用多种方法对这些数进行排序，然后分析各自的所需的排序时间找出较快的排序算法。1.2设计要求1)分别采用的排序算法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序，实现这批数据的排序，并把排序后的结果保存在不同的文件中。2)统计每一种排序算法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的算法。xxxxx《xxxxx》课程设计报告22需求分析2.1直接插入排序思路:设有一组关键字{K1,K2,…….,Kn},排序开始变认为K1是一个有序的序列,让K2插入到表长为1的有序序列,使之成为一个表长为2的有序序列,让K3插入到表长为2的有序序列,使之成为一个表长为3的有序序列,依次类推,最后让Kn插入上述表长为n-1的有序序列,得到一个表长为n的有序序列.2.2希尔排序思路：先取一个正整数d1(d1n),把全部记录分成d1个组,所有距离为d1的倍数的记录看成是一组,然后在各组内进行插入排序;然后取d2(d2d1),重复上述分组和排序操作,直到取di=1(=1),即所有记录成为一个组为此.一般选d1约为n/2,d2为d1/2,…….,di=12.3快速排序:（递归和非递归）思路:以第一个关键字K1为控制字，将[K1、K2、….Kn]分成两个子区，使左区的有关键字小于等于K1，右区所有关键字大于等于K1，最后控制居两个子区中间的适当位置。在子区内数据尚处于无序状态。将右区首、尾指针保存入栈，对左区进行与第（1）步相