排序综合实验资料报告材料

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

2、分成若干组，所有相隔为某个“增量”的记录为一组，在各组进 行直接插入排序；初始时增量 d1 较大，分组较多（每组的记录数少） ，以后增量逐渐减少， 分组减少 （每组的记录数增多） ，直到最后增量为 1（ d1>d2>.>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 CP

6、U M 4802.67GHzXX存4.00 GB (金士顿 PC3-10600 DDR3 1333MHz)学号xxxxxxxxxx主板宏碁 JE40_CP班级10电信1班操作系统Microsoft Windows 7旗舰版 (64 位/Service Pack 1)xxxxxxxxxxxxx编译软件Visual C+ 6.0email609803959qq.10A42*10A410A52*10A510A62*10A610A72*10A710A81QA5正序逆序直接插入（带监视哨）tC24.874100.1582500.39995.60.0999995000.05（时间）0.1560.54613

7、.39153.417>5min027.486直接插入（无监视哨）tC24.874100.1582500.39995.60.0999994999.950.1560.57814.2156.715>5min029.137希尔排序（无监视哨）tC0.261664 0598651 4.291069.6094670.5165166.9291084.562461.3717159.61.500012.244580.0150.0160.0470.1090.7171.59111.54427.735208.7220.020.02直接选择tC0000000.2180.7819.36777.32>5m

8、in19.75120.249冒泡（上升）C49.9905199.9854999.9419999.90.0999994999.950.4521.82545.542182.678>5min047.326冒泡（下沉）C49.9904199.964999.7819999.90.0999994999.950.4831.90247.239189.081>5min047.503快速（递归）tC0.170775 0361618 2.170424.7964625.812557.6668320.86647.4543493.62201.32201.40.010.010.0310.0620.2190.48

9、42.5775.29729.37718.02618.195堆排序（非递归）tC0.235479 0510793 3.(19386.4389536.793277.5876434.639909.2815012.883.112522.926640.0160.0160.0470.0940.4990.9687.22317.093123.4290.040.05堆排序（递归）tC0.235479 0510793 3.019386.4389536.793277.5876434.639909.2815012.883.112522.9266400.0150.0780.1250.9031.82513.65931.7

10、42235.3460.060.07二路归并（非递归）tC0.123676 0267361 1.566513.3330518.716639.4319224.002468.0062540.150.8779860.81502400.0150.0460.0620.250.5463.0176.45735.3090.030.03实验结果原因分析和结论：1. 插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较 快的速度。反而在这种情况下，快速排序反而慢了。当 n 较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。 若待排序的记录的关键字在一个明显有限围时

11、,且空间允许是用桶排序。当 n 较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。当 n 较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下。 宜用归并排序。当 n 较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。2. 插入排序、冒泡排序、选择排序的时间复杂性为 O（n2） 其它非线形排序的时间复杂性为 O（nlog2n） 线形排序的时间复杂性为 O（n）;3. 在算法运行期间，运行 QQ软件、360安全卫士、 360杀毒、word文档、ppt、酷狗等软件 会影响绝对时间和逻辑时间，使时间增大4. 随着 n 的取值增大，算法的实际时间增长速度

12、逐渐增大。5. 直接插入排序（有、无监视哨） 、冒泡排序（上升、下沉） 、堆排序（递归、非递归）的关 键字比较次数相同， 但绝对时间相差比较大； 直接选择排序与冒泡排序的关键字比较次数相 近。6. 相比较其他同学的数据，直接插入（有、无监视哨） ，直接选择，冒泡（上升、下沉）的 结果相差较小， 希尔选择结果相差很大， 另快速 （递归），堆（递归， 非递归），二路归并 （非 递归）结果并不会受计算机环境而不同。附录：源程序极其代码#define CPP C+#define MPP M+#define MP2 M+=2#define MP3 M+=3#include <fstream.h&g

13、t;#include <iomanip.h>#include <stdlib.h>#include <time.h>#include <math.h>const int maxsize=20000;/排序表容量typedef int datatype;typedef struct datatype key;/关键字域/ othertype other;/其它域 rectype;/ 记录类型typedef rectype listmaxsize+2; / 排序表类型， 0 号单元不用_int64 C,M;/比较和移动次数void check(lis

14、t R,int n) / 检验排序结果int i;for(i=2;i<=n;i+)if(Ri.key<Ri-1.key) cout<<"Error!n"return; cout<<"Correct! "void disp(list R,int n) / 显示排序后的结果int i;for(i=1;i<=n;i+) cout<<setw(4)<<Ri.key<<" "/ if(i%20=0) cout<<endl;cout<<endl;

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

16、int n) / 直接插入排序，无监视哨int i,j;rectype x;/x 为辅助量 (用 R0 代替时间变长 )for(i=2;i<=n;i+) /进行 n-1 次插入if(CPP,Ri.key>=Ri-1.key) continue;MPP,x=Ri;/ 待排记录暂存到 xj=i-1;do / 顺序比较和移动MPP,Rj+1=Rj;j-; while(j>=1 && (CPP,x.key<Rj.key);MPP,Rj+1=x;/ 插入 Rivoid ShellSort1(list R,int n)/ 一趟插入排序， h 为本趟增量int h,i

17、,j,k;for(h=n/2;h>=1;h=h/2)for(i=1;i<=h;i+)/i 为组号for(j=i+h;j<=n;j+=h)/每组从第 2 个记录开始插入if(CPP,Rj.key>=Rj-h.key) continue;/Rj 大于有序区最后一个记录， /则不需要插入 MPP,R0=Rj;/R0 保存待插入记录，但不是监视哨k=j-h;/ 待插记录的前一个记录do/ 查找正确的插入位置MPP,Rk+h=Rk;k=k-h;/ 后移记录，继续向前搜索 while(k>0&&(CPP,R0.key<Rk.key);MPP,Rk+h=R

18、0;/ 插入 Rjif(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.key<Rk.key) k=j;if(k!=i)R0=Ri;Ri=Rk;Rk=R0;/交换 Ri 和 R0 ，R0 作辅助量void BubbleSort1(list R,int n) / 上升法冒泡排序 int i,j,flag;rectype x; for(i=1;i<=n-1;i+) f

19、lag=0; for(j=n;j>=i+1;j-)/x为辅助量（可用R0代替）/做 n-1 趟扫描/置未交换标志/从下向上扫描/交换记录if(CPP,Rj.key<Rj-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; for(j=1;j<=n-i;j+)/X为辅助量（可用R0代替）/做 n-

20、1 趟扫描 /置未交换标志 /从上向下扫描if(CPP,Rj.key>Rj+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) && i<j) j-;/从右

21、向左扫描 (取消=变快)if(i<j) MPP,Ri=Rj;i+;/交换 Ri 和 Rjwhile(CPP,Ri.key<=x.key) && i<j) i+;/ 从左向右扫描if(i<j) MPP,Rj=Ri;j-;/交换 Ri 和 Rj while(i<j);MPP,Ri=x;/ 基准移到最终位置return i; / 最后 i=jvoid QuickSort1(list R,int s,int t) / 对 Rs到 Rt快速排序，递归算法mint i;if(s>=t) return;/只有一个记录或无记录时无需排序i=Partition

22、(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 的左孩子if(j<q && (CPP,Rj.key<Rj+1.key) j+;/j 指向 Rp 的右孩子if(CPP,R0.key>=Rj.key) break;/根结点键值大于孩子结点，已经是堆，调整

23、结束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(j>q) return;/只有一个元素或无元素if(j<q && (CPP,Rj.key<Rj+1.key) j+;/j 指向 Rp 的右孩子if(CPP,Rp.key>=Rj.key) return;/根结点关键字已最

24、大MPP,R0=Rj;MPP,Rj=Rp;MPP,Rp=R0;/交换Rj和Rp , R0作辅助量Sift2(R,j,q);/递归void HeadSort1(list R,int n)堆R1到Rn进行堆排序/建初始堆/进行 n-1 趟堆排序/堆顶和当前堆底交换，R0作辅助量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;/R1 到 Ri-1 重建成新堆Sift1(R,1,i-1);else/子表个数为奇数 ,剩一段void HeadSort2(list R,i

25、nt n) int i;for(i=n/2;i>=1;i-) Sift2(R,i,n); for(i=n;i>=2;i-)MPP,R0=R1;MPP,R1=Ri;MPP,Ri=R0;Sift2(R,1,i-1);/堆R1到Rn进行堆排序/建初始堆/进行 n-1 趟堆排序/堆顶和当前堆底交换，R0作辅助量/R1 到 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;/取小者

26、复制/复制左子表的剩余记录/复制右子表的剩余记录k=low; while(i<=mid && j<=high) if(CPP,Ri.key<=Rj.key) MPP,R1k+=Ri+; else MPP,R1k+=Rj+;while(i<=mid) 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; /i 指向第一对子表的起始点 while(i+2*len-1&

27、lt;=n) /归并长度为 len 的两个子表Merge(R,R1,i,i+len-1,i+2*len-1);i=i+2*len;/i 指向下一对子表起始点if(i+len-1<n)/剩下两个子表，其中一个长度小于lenMerge(R,R1,i,i+len-1,n);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<n) MergePass(R,R1,n,le

28、n);len=len*2;/一趟归并，结果在 R1 中MergePass(R1,R,n,len);len=len*2;/再次归并，结果在 R 中int random1(int num) return rand(); /0RAND_MAX=32767int random3(int num) / 素数模乘同余法 ,0Mint A=16807; / 16807,39722040,764261123,630360016 48271?int M=2147483647; /有符号4字节最大素数，2人31-1int Q=M/A;int R=M%A;static int x=1，n=0，g=0; /seed(

29、set to 1)static double r，r1=0，r2=0;int x1;x1=A*(x%Q)-R*(x/Q);if(x1>=0) x=x1;else x=x1+M;r=1.*x/M;if(r>0.5) g+;n+;r1+=r;r2+=r*r;if(n%maxsize=0) cout<<"x="<<r<<" "<<g<<" "<<"n="<<n<<" "<<r1/n&

30、lt;<" "<<r2/n<<" "<<(r2-r1)/n+.25<<endl; return 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

31、) 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);/生成 0-n 之间的随机数do C=M=0;/取出初始数据用于排序for(i=1;i<=n;i+)Ri