《排序综合实验报告》由会员分享，可在线阅读，更多相关《排序综合实验报告（13页珍藏版）》请在金锄头文库上搜索。
1、数据结构排序算法综合实验报告姓 名：xx x x 班 级：10电信1学 号：xxx 指导老师：胡圣荣日期: 2012.12.152013。1。5华南农业大学工程学院算法基本思想：1、插入排序：每次将一个待排序的记录，按其关键字大小插入到前面已经排序好的序列中的适当位置，直到全部记录插入完毕为止。（1）直接插入排序：在排序过程中，每次都讲无序区中第一条记录插入到有序区中适当位置，使其仍保持有序。初始时，取第一条记录为有序区,其他记录为无序区。显然，随着排序过程的进行，有序区不断扩大,无序区不断缩小。最终无序区变为空,有序区中包含了所有的记录,排序结束.（2)希尔排序：将排序表分成若干组，所有相隔
2、为某个“增量”的记录为一组，在各组内进行直接插入排序；初始时增量d1较大,分组较多（每组的记录数少），以后增量逐渐减少，分组减少（每组的记录数增多），直到最后增量为1（d1d2。.dt=1），所有记录放为一组，再整体进行一次直接插入排序。2、交换排序：每次比较两个待排序的记录，如果发现他们关键字的次序与排序要求相反时就交换两者的位置，直到没有反序的记录为止。（1）冒泡排序：设想排序表R1到Rn垂直放置，将每个记录Ri看作是重量为Ri.key的气泡；根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡违反本原则的轻气泡，就使其向上“漂浮，如此反复进行，直到最后任何两个气泡都是轻者在上,重者在
3、下为止。（2）快速排序:在待排序的n个记录中任取一个作为“基准”，将其与记录分为两组,第一组中个记录的键值均小于或等于基准的键值,第二组中个记录的键值均大于或等于基准的键值，而基准就排在这两组中间（这也是该记录的最终位置），这称为一趟快速排序（或一次划分）.对所分成的两组重复上述方法，直到所有记录都排在适当位置为止。3、选择排序：每次从待排序的记录中选出关键字最小(或最大）的记录，顺序放在已排好序的子序列的后面（或最前），直到全部记录排序完毕。（1）直接选择排序：首先,所有记录组成初始无序区R1到Rn，从中选出键值最小的记录，与无序区第一个记录R1交换；新的无序区为R2到Rn，从中再选出键值最
4、小的记录,与无序区第一个记录R2交换；类似，第i趟排序时R1到Ri1是有序区，无序区为Ri到Rn,从中选出键值最小的记录，将它与无序区第一个记录Ri交换,R1到Ri变为新的有序区。因为每趟排序都使有序区中增加一个记录，所以,进行n1趟排序后，整个排序表就全部有序了。（2）堆排序:利用小根堆（或大根堆）来选取当前无序区中关键字最小（或最大)的记录来实现排序的。下面介绍利用大根堆来排序。首先,将初始无序区调整为一个大根堆，输出关键字最大的堆顶记录后，将剩下的n-1个记录在重建为堆，于是便得到次小值。如此反复执行，知道全部元素输出完，从而得到一个有序序列。4、并归排序：指将若干个已排序的子表合成一个
5、有序表.（1）二路并归排序:开始时，将排序表R1到Rn看成n个长度为1的有序子表,把这些子表两两并归，便得到n/2个有序的子表（当n为奇数时，并归后仍是有一个长度为1的子表）；然后，再把这n/2个有序的子表两两并归，如此反复，直到最后得到一个程度为n的有序表为止。各种排序实验结果：CPU（英特尔)Intel(R) Core(TM） i5 CPU M 480 2。67GHz姓名xx内存4.00 GB （金士顿 PC3-10600 DDR3 1333MHz）学号xxxxxxxxxx主板宏碁 JE40_CP班级10电信1班操作系统Microsoft Windows 7 旗舰版 （64位/Servic
6、e Pack 1）电话xxxxxxxxxxxxx编译软件Visual C+ 6.0email609803959qq。com1042*1041052*10510621061072*107108105正序逆序直接插入（带监视哨）C24.874100。1582500.39995.60.0999995000.05t(时间）0。1560。54613.39153.4175min027.486直接插入(无监视哨）C24。874100。1582500。39995。60.0999994999。95t0.1560.57814。2156。7155min029.137希尔排序（无监视哨)C0.2616640。5986
7、514。291069。6094670.5165166。9291084.562461.3717159。61。500012.24458t0.0150.0160.0470.1090.7171.59111.54427。735208.7220。020.02直接选择C000000t0.2180.7819。36777.325min19.75120.249冒泡(上升）C49.9905199.9854999。9419999.90.0999994999。95t0.4521。82545.542182.6785min047.326冒泡（下沉)C49。9904199.964999.7819999。90.09999949
8、99。95t0.4831.90247。239189。0815min047.503快速（递归）C0.1707750.3616182.170424.7964625。812557。6668320。86647。4543493。62201.32201。4t0.010.010.0310。0620.2190.4842。5775。29729。37718.02618.195堆排序(非递归) C0.2354790。5107933。019386。4389536.793277。5876434。639909。2815012。883.112522。92664t0.0160。0160.0470。0940.4990。9687
9、。22317.093123。4290。040.05堆排序(递归)C0.2354790.5107933.019386。4389536.793277。5876434.639909.2815012.883.112522。92664t00。0150。0780。1250。9031.82513.65931。742235.3460。060.07二路归并(非递归） C0.1236760.2673611.566513。3330518。716639.4319224。002468。0062540.150。8779860.815024t00。0150.0460。0620。250.5463.0176.45735.309
10、0.030。03实验结果原因分析和结论：1. 插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了。当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。若待排序的记录的关键字在一个明显有限范围内时，且空间允许是用桶排序.当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。当n较大时，关键字元素可能出现本身是有序的,对稳定性有要求时，空间允许的情况下。宜用归并排序.当n较大时,关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。2.插入排序、冒泡排序、选择排序的时间复杂性为O(n2)
11、其它非线形排序的时间复杂性为O(nlog2n)线形排序的时间复杂性为O（n）;3.在算法运行期间，运行QQ软件、360安全卫士、360杀毒、word文档、ppt、酷狗等软件会影响绝对时间和逻辑时间，使时间增大4。随着n的取值增大，算法的实际时间增长速度逐渐增大.5.直接插入排序（有、无监视哨）、冒泡排序（上升、下沉）、堆排序（递归、非递归）的关键字比较次数相同,但绝对时间相差比较大；直接选择排序与冒泡排序的关键字比较次数相近.6。相比较其他同学的数据，直接插入（有、无监视哨），直接选择，冒泡(上升、下沉）的结果相差较小,希尔选择结果相差很大，另快速（递归),堆（递归，非递归),二路归并（非递归
12、)结果并不会受计算机环境而不同。附录：源程序极其代码#define CPP C+define MPP M+#define MP2 M+=2#define MP3 M+=3include fstream。hinclude iomanip.hinclude include time。h#include const int maxsize=20000; /排序表容量typedef int datatype；typedef struct datatype key； /关键字域/ othertype other; /其它域 rectype； /记录类型typedef rectype listmaxsiz
13、e+2; /排序表类型，0号单元不用_int64 C，M； /比较和移动次数void check（list R,int n) /检验排序结果 int i； for(i=2;i=n;i+) if（Ri.keyRi1.key) cout”Error!n”;return; coutCorrect! ”;void disp（list R,int n） /显示排序后的结果 int i; for（i=1；i=n;i+) coutsetw(4)Ri.key ；/ if(i%20=0） coutendl； coutendl；void InsertSort1(list R,int n） /直接插入排序，带监视哨(并不改变关键字次数) int
