排序综合实验报告

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

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

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

4、录组成初始无序区 R1 到 Rn ，从中选出键值最小的记 录，与无序区第一个记录 R1交换；新的无序区为 R2到Rn，从中再选出键值最小的记 录，与无序区第一个记录 R2 交换；类似，第 i 趟排序时 R1 到 Ri-1 是有序区，无序区 为 Ri 到 Rn ，从中选出键值最小的记录， 将它与无序区第一个记录 Ri 交换， R1 到 Ri 变为新的有序区。因为每趟排序都使有序区中增加一个记录，所以，进行 n-1 趟排序后，整 个排序表就全部有序了。 （2）堆排序：利用小根堆（或大根堆）来选取当前无序区中关键字最小（或最大）的记录 来实现排序的。 下面介绍利用大根堆来排序。 首先，将初始无序区调

5、整为一个大根堆， 输出 关键字最大的堆顶记录后， 将剩下的 n-1 个记录在重建为堆， 于是便得到次小值。 如此反复 执行，知道全部元素输出完，从而得到一个有序序列。 4、并归排序 ：指将若干个已排序的子表合成一个有序表。 （1）二路并归排序：开始时，将排序表 R1到Rn看成n个长度为1的有序子表，把这些 子表两两并归， 便得到 n/2 个有序的子表 （当 n 为奇数时， 并归后仍是有一个长度为 1 的子 表）；然后，再把这 n/2 个有序的子表两两并归，如此反复，直到最后得到一个程度为n 的 有序表为止。 各种排序实验结果: CPU (英特尔)lntel(R) Core(TM) i5 CPU

6、 M 480 2.67GHz 姓名 XX 内存 4.00 GB (金士顿 PC3-10600 DDR3 1333MHz) 学号 xxxxxxxxxx 主板 宏碁 JE40_CP 班级 10电信1班 操作系统 Microsoft Windows 7旗舰版 (64 位/Service Pack 1) 电话 xxxxxxxxxxxxx 编译软件 Visual C+ 6.0 email 10A4 2*10A4 10A5 2*10A5 10A6 2*10A6 10A7 2*10A7 10A8 1QA5 正序 逆序 直接插入 （带监视哨）t C 24.874 100.158 2500.3 9995.6 0

7、.099999 5000.05 （时间） 0.156 0.546 13.391 53.417 5min 0 27.486 直接插入 （无监视哨）t C 24.874 100.158 2500.3 9995.6 0.099999 4999.95 0.156 0.578 14.21 56.715 5min 0 29.137 希尔排序 （无监视哨）t C 0.261664 0 598651 4.2 9106 9.60946 70.5165 166.929 1084.56 2461.37 17159.6 1.50001 2.24458 0.015 0.016 0.047 0.109 0.717 1.5

8、91 11.544 27.735 208.722 0.02 0.02 直接选择t C 0 0 0 0 0 0 0.218 0.78 19.367 77.32 5min 19.751 20.249 冒泡（上升） C 49.9905 199.985 4999.94 19999.9 0.099999 4999.95 0.452 1.825 45.542 182.678 5min 0 47.326 冒泡（下沉） C 49.9904 199.96 4999.78 19999.9 0.099999 4999.95 0.483 1.902 47.239 189.081 5min 0 47.503 快速（递归

9、）t C 0.170775 0 361618 2.1 7042 4.79646 25.8125 57.6668 320.86 647.454 3493.6 2201.3 2201.4 0.01 0.01 0.031 0.062 0.219 0.484 2.577 5.297 29.377 18.026 18.195 堆排序 （非递归）t C 0.235479 0 510793 3.( 1938 6.43895 36.7932 77.5876 434.639 909.281 5012.88 3.11252 2.92664 0.016 0.016 0.047 0.094 0.499 0.968 7

10、.223 17.093 123.429 0.04 0.05 堆排序 （递归）t C 0.235479 0 510793 3.0 1938 6.43895 36.7932 77.5876 434.639 909.281 5012.88 3.11252 2.92664 0 0.015 0.078 0.125 0.903 1.825 13.659 31.742 235.346 0.06 0.07 二路归并 （非递归）t C 0.123676 0 267361 1.5 6651 3.33305 18.7166 39.4319 224.002 468.006 2540.15 0.877986 0.815

11、024 0 0.015 0.046 0.062 0.25 0.546 3.017 6.457 35.309 0.03 0.03 实验结果原因分析和结论： 1. 插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较 快的速度。反而在这种情况下，快速排序反而慢了。 当 n 较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。 若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。 当 n 较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。 当 n 较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下。 宜用归

12、并排序。 当 n 较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。 2. 插入排序、冒泡排序、选择排序的时间复杂性为 O（n2） 其它非线形排序的时间复杂性为 O（nlog2n） 线形排序的时间复杂性为 O（n）; 3. 在算法运行期间，运行 QQ软件、360安全卫士、 360杀毒、word文档、ppt、酷狗等软件 会影响绝对时间和逻辑时间，使时间增大 4. 随着 n 的取值增大，算法的实际时间增长速度逐渐增大。 5. 直接插入排序（有、无监视哨） 、冒泡排序（上升、下沉） 、堆排序（递归、非递归）的关 键字比较次数相同， 但绝对时间相差比较大； 直接选择排序与冒泡排序的

13、关键字比较次数相 近。 6. 相比较其他同学的数据，直接插入（有、无监视哨） ，直接选择，冒泡（上升、下沉）的 结果相差较小， 希尔选择结果相差很大， 另快速（递归），堆（递归， 非递归），二路归并 （非 递归）结果并不会受计算机环境而不同。 附录：源程序极其代码 #define CPP C+ #define MPP M+ #define MP2 M+=2 #define MP3 M+=3 #include #include #include #include #include const int maxsize=20000;/排序表容量 typedef int datatype; typed

14、ef struct datatype key;/关键字域 / othertype other;/其它域 rectype;/ 记录类型 typedef rectype listmaxsize+2; / 排序表类型， 0 号单元不用 _int64 C,M;/比较和移动次数 void check(list R,int n) / 检验排序结果 int i; for(i=2;i=n;i+) if(Ri.keyRi-1.key) coutError!n;return; coutCorrect! ; void disp(list R,int n) / 显示排序后的结果 int i; for(i=1;i=n;

15、i+) coutsetw(4)Ri.key ; / if(i%20=0) coutendl; coutendl; void InsertSort1(list R,int n) / 直接插入排序，带监视哨 ( 并不改变关键字次数 ) int i,j; for(i=2;i=Ri-1.key) continue; /Ri 大于有序区最后一个记录，则本趟不需插入 MPP,R0=Ri;/R0 是监视哨 j=i-1; do /查找 Ri 的插入位置 MPP,Rj+1=Rj;j-;/ 记录后移，继续向前搜索 while(CPP,R0.keyRj.key); MPP,Rj+1=R0;/ 插入 Ri void

16、InsertSort2(list R,int n) / 直接插入排序，无监视哨 int i,j;rectype x;/x 为辅助量 (用 R0 代替时间变长 ) for(i=2;i=Ri-1.key) continue; MPP,x=Ri;/ 待排记录暂存到 x j=i-1; do / 顺序比较和移动 MPP,Rj+1=Rj;j-; while(j=1 h=h/2) for(i=1;i=h;i+)/i 为组号 for(j=i+h;j=Rj-h.key) continue;/Rj 大于有序区最后一个记录， /则不需要插入 MPP,R0=Rj;/R0 保存待插入记录，但不是监视哨 k=j-h;/

17、待插记录的前一个记录 do/ 查找正确的插入位置 MPP,Rk+h=Rk;k=k-h;/ 后移记录，继续向前搜索 while(k0 MPP,Rk+h=R0;/ 插入 Rj if(h=1) break; void SelectSort1(list R,int n) int i,j,k; for(i=1;i=n-1;i+)/n-1 趟排序 k=i; for(j=i+1;j=n;j+)/ 在当前无序区从前向后找键值最小的记录 Rk if(Rj.keyRk.key) k=j; if(k!=i)R0=Ri;Ri=Rk;Rk=R0;/交换 Ri 和 R0 ，R0 作辅助量 void BubbleSort1

18、(list R,int n) / 上升法冒泡排序 int i,j,flag;rectype x; for(i=1;i=i+1;j-) /x为辅助量（可用R0代替） /做 n-1 趟扫描 /置未交换标志 /从下向上扫描 /交换记录 if(CPP,Rj.keyRj-1.key) flag=1; MP3,x=Rj;Rj=Rj-1;Rj-1=x;/ 交换 if(!flag) break; /本趟未交换过记录，排序结束 void BubbleSort2(list R,int n) / 下沉法，冒泡排序 int i,j,flag;rectype x; for(i=1;i=n-1;i+) flag=0; f

19、or(j=1;jRj+1.key) / 交换记录 flag=1; MP3,x=Rj;Rj=Rj+1;Rj+1=x;/ 交换 if(!flag) break; /本趟未交换过记录，排序结束 int Partition(list R,int p,int q) / 对 Rp 到 Rq 划分，返回基准位置 int i,j;rectype x;/辅助量(可用 R0代替) i=p;j=q;MPP,x=Rp;/x 存基准 (无序区第一个记录 ) do while(CPP,Rj.key=x.key) /从右向左扫描 (取消=变快) if(ij) MPP,Ri=Rj;i+;/交换 Ri 和 Rj while(C

20、PP,Ri.key=x.key) / 从左向右扫描 if(ij) MPP,Rj=Ri;j-;/交换 Ri和 Rj while(i=t) return; /只有一个记录或无记录时无需排序 i=Partition(R,s,t); 对Rs到Rt做划分 QuickSort1(R,s,i-1); /递归处理左区间 QuickSort1(R,i+1,t); /递归处理右区间 void Sift1(list R,int p,int q) 算法 /堆范围为 RpRq, 调整 Rp 为堆， 非递归 int j; MPP,R0=Rp; /R0 作辅助量 j=2*p; while(j=q) /j 指向 Rp 的左孩

21、子 if(jq /根结点键值大于孩子结点，已经是堆， 调整结束 MPP,Rp=Rj; p=j; j=2*p; MPP,Rp=R0; /将 Rj 换到双亲位置上 /修改当前被调整结点 /j 指向 Rp 的左孩子 /原根结点放入正确位置 void Sift2(list R,int p,int q) 法 /堆范围为 RpRq, 调整 Rp 为堆， 递归算 int j; if(p=q) return; j=2*p; if(jq) return; /只有一个元素或无元素 if(jq /根结点关键字已最大 MPP,R0=Rj; /交换Rj和Rp , R0作辅助量 MPP,Rj=Rp; MPP,Rp=R0;

22、 Sift2(R,j,q); /递归 void HeadSort1(list R,int n) 堆R1到Rn进行堆排序 int i; for(i=n/2;i=1;i-) Sift1(R,i,n); for(i=n;i=2;i-) MPP,R0=R1; MPP,R1=Ri; MPP,Ri=R0; Sift1(R,1,i-1); /建初始堆 /进行 n-1 趟堆排序 /堆顶和当前堆底交换，R0作辅助量 /R1 到 Ri-1 重建成新堆 void HeadSort2(list R,int n) II堆R1到Rn进行堆排序 int i; for(i=n/2;i=1;i-) Sift2(R,i,n);

23、for(i=n;i=2;i-) MPP,R0=R1; MPP,R1=Ri; MPP,Ri=R0; Sift2(R,1,i-1); /建初始堆 II进行n-1趟堆排序 II堆顶和当前堆底交换，R0作辅助量 IIR1 到 Ri-1 重建成新堆 void Merge(list R,list R1,int low,int mid,int high) /合并 R 的两个子表： RlowRmid 、 Rmid+1Rhigh ，结果在 R1 中 int i,j,k; i=low; j=mid+1; k=low; while(i=mid /取小者复制 else MPP,R1k+=Rj+; while(i=mi

24、d) MPP,R1k+=Ri+;/复制左子表的剩余记录 while(j=high) MPP,R1k+=Rj+;/ 复制右子表的剩余记录 void MergePass(list R,list R1,int n,int len) / 对 R 做一趟归并，结果在 R1 中 int i,j; i=1; while(i+2*len-1=n) IIi 指向第一对子表的起始点 II归并长度为len的两个子表 Merge(R,R1,i,i+len-1,i+2*len-1); i=i+2*len; 1 IIi 指向下一对子表起始点 if(i+len-1n) Merge(R,R1,i,i+len-1,n); II

25、剩下两个子表，其中一个长度小于len else/ 子表个数为奇数 ,剩一段 for(j=i;j=n;j+)/ 将最后一个子表复制到R1 中 MPP,R1j=Rj; void MergeSort(list R,list R1,int n) / 对 R 二路归并排序，结果在 R 中 (非递归算法 ) int len; len=1; while(len=0) x=x1; else x=x1+M; r=1.*x/M;if(r0.5) g+; n+;r1+=r;r2+=r*r; if(n%maxsize=0) coutx=r g n=n r1/n r2/n (r2-r1)/n+.25endl; retu

26、rn x; void main() rectype *R,*R1,*S;R1用于归并排序的辅助存储，S用于保存初始排序数据 R=new list;if(R=NULL) cout 数组太大 !n;exit(-1); R1=new list;if(R1=NULL) cout 数组太大 !n;exit(-1); S=new list;if(S=NULL) cout 数组太大 !n;exit(-1); int i,n=maxsize; int choice; clock_t t1,t2; / float s,t; / 正序序列 / for(i=1;i=n;i+) / Si.key=i; /反序序列 / for(i=1;i=n;i+) / Si.key=n-i+1; / srand( (unsigned)time( NULL ) ); for(i=1;i=n;i+) Si.key=random3(n);/生