《基本排序算法综合实验》由会员分享，可在线阅读，更多相关《基本排序算法综合实验（13页珍藏版）》请在金锄头文库上搜索。
1、基本排序算法综合实验一、计算条件：CPU：E5200内存：2G主板：华硕P5KPL SE操作系统：Windows 7 旗舰版编译软件：C-Free4.1其它： 运行QQ软件、360安全卫士、360杀毒、word文档、ppt、酷狗等软件二、源程序代码#define CPP C+#define MPP M+#define MP2 M+=2#define MP3 M+=3#include #include #include #include #include const int maxsize=100000; /排序表容量typedef int datatype;typedef struct dat
2、atype 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;i+) coutsetw(4)Ri.ke
3、y ;/ 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 InsertSort2(list R,int n) /直接插
4、入排序，无监视哨 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 & (CPP,x.key=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; /待插记录的前一个记录 do /查找正确的插入位置 M
5、PP,Rk+h=Rk;k=k-h;/后移记录，继续向前搜索 while(k0&(CPP,R0.keyRk.key);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+)/在当前无序区从前向后找键值最小的记录Rkif(Rj.keyRk.key) k=j;if(k!=i)R0=Ri;Ri=Rk;Rk=R0;/交换Ri和R0，R0作辅助量 void BubbleSort1(list R,int n) /上升法
6、冒泡排序 int i,j,flag;rectype x; /x为辅助量(可用R0代替) for(i=1;i=i+1;j-) /从下向上扫描 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; /x为辅助量(可用R0代替) for(i=1;i=n-1;i+) /做n-1趟扫描 flag=0; /置未交换标志 for(j=1;jR
7、j+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) & ij) j-;/从右向左扫描(取消=变快) if(ij) MPP,Ri=Rj;i+; /交换Ri和Rj while(CPP,Ri.key=x.
8、key) & ij) i+;/从左向右扫描 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; /j指向Rp的左孩子while(j=q)if(jq & (CPP,Rj.key=Rj.key) break; /根结点键值大于孩子结点，已经是堆，调整结束MPP,Rp=Rj; /将Rj换到双亲位置上p=j; /修改当前被调整结点j=2*p; /j指向Rp的左孩子MPP,Rp=R0; /原根结点放入正确位置void Sift2(list R,int p,int q) /堆范围为RpRq,调整Rp为堆，递归算法int j;if(p=q) return; /只有一个元素或无元素j
