排序综合实验报告材料.doc

《排序综合实验报告材料.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构排序算法综合实验报告姓名：xxxx班级：10电信1学号：xxx指导老师：胡圣荣日期：2012.12.15～2013.1.5华南农业大学工程学院算法基本思想：1、插入排序：每次将一个待排序的记录，按其关键字大小插入到前面已经排序好的序列中的适当位置，直到全部记录插入完毕为止。（1）直接插入排序：在排序过程中，每次都讲无序区中第一条记录插入到有序区中适当位置，使其仍保持有序。初始时，取第一条记录为有序区，其他记录为无序区。显然，随着排序过程的进行，有序区不断扩大，无序区不断缩小。最终无序区变为空，有序区中包含了所有的记录，排序结束

2、。（2）希尔排序：将排序表分成若干组，所有相隔为某个“增量”的记录为一组，在各组进行直接插入排序；初始时增量d1较大，分组较多（每组的记录数少），以后增量逐渐减少，分组减少（每组的记录数增多），直到最后增量为1（d1>d2>...>dt=1）,所有记录放为一组，再整体进行一次直接插入排序。2、交换排序：每次比较两个待排序的记录，如果发现他们关键字的次序与排序要求相反时就交换两者的位置，直到没有反序的记录为止。（1）冒泡排序：设想排序表R[1]到R[n]垂直放置，将每个记录R[i]看作是重量为R[i].key的气泡；根据轻气泡不能在重气

3、泡之下的原则，从下往上扫描数组R，凡违反本原则的轻气泡，就使其向上“漂浮”，如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。（2）快速排序：在待排序的n个记录中任取一个作为“基准”，将其与记录分为两组，第一组中个记录的键值均小于或等于基准的键值，第二组中个记录的键值均大于或等于基准的键值，而基准就排在这两组中间（这也是该记录的最终位置），这称为一趟快速排序（或一次划分）。对所分成的两组重复上述方法，直到所有记录都排在适当位置为止。3、选择排序：每次从待排序的记录中选出关键字最小（或最大）的记录，顺序放在已排好序的子序列的

4、后面（或最前），直到全部记录排序完毕。（1）直接选择排序：首先，所有记录组成初始无序区R[1]到R[n]，从中选出键值最小的记录，与无序区第一个记录R[1]交换；新的无序区为R[2]到R[n]，从中再选出键值最小的记录，与无序区第一个记录R[2]交换；类似，第i趟排序时R[1]到R[i-1]是有序区，无序区为R[i]到R[n]，从中选出键值最小的记录，将它与无序区第一个记录R[i]交换，R[1]到R[i]变为新的有序区。因为每趟排序都使有序区中增加一个记录，所以，进行n-1趟排序后，整个排序表就全部有序了。（2）堆排序：利用小根堆（或

5、大根堆）来选取当前无序区中关键字最小（或最大）的记录来实现排序的。下面介绍利用大根堆来排序。首先，将初始无序区调整为一个大根堆，输出关键字最大的堆顶记录后，将剩下的n-1个记录在重建为堆，于是便得到次小值。如此反复执行，知道全部元素输出完，从而得到一个有序序列。4、并归排序：指将若干个已排序的子表合成一个有序表。（1）二路并归排序：开始时，将排序表R[1]到R[n]看成n个长度为1的有序子表，把这些子表两两并归，便得到n/2个有序的子表（当n为奇数时，并归后仍是有一个长度为1的子表）；然后，再把这n/2个有序的子表两两并归，如此反复，

6、直到最后得到一个程度为n的有序表为止。各种排序实验结果：　CPU(英特尔)Intel(R)Core(TM)i5CPUM4802.67GHz　xx存4.00GB(金士顿PC3-10600DDR31333MHz)学号　xxxxxxxxxx主板宏碁JE40_CP班级　10电信1班操作系统MicrosoftWindows7旗舰版(64位/ServicePack1)　xxxxxxxxxxxxx编译软件VisualC++6.0email　609803959qq.　　10^42*10^410^52*10^510^62*10^610^72*10^71

7、0^810^5正序逆序直接插入(带监视哨）C24.874100.1582500.39995.60.0999995000.05t(时间)0.1560.54613.39153.417>5min027.486直接插入(无监视哨）C24.874100.1582500.39995.6　0.0999994999.95t0.1560.57814.2156.715>5min029.137希尔排序(无监视哨)C0.2616640.5986514.291069.6094670.5165166.9291084.562461.3717159.61.50001

8、2.24458t0.0150.0160.0470.1090.7171.59111.54427.735208.7220.020.02直接选择C000000t0.2180.7819.36777.32>5min19.75120