排序算法实验

《排序算法实验》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析上机实验报告班级：学号：姓名：排序算法：直接插入排序、归并排序、快速排序和随机快速排序1、直接插入排序（1）核心代码：#include#include#include#include"assert.h"usingnamespacestd;structSqList{int*key;intlength;};voidCreateSqList(SqList&sl){srand((unsigned)time(NULL));//srand()函数产生一个以当前时

2、间开始的随机种子sl.length=10000;sl.key=newint[sl.length+1];assert(sl.key);for(inti=1;i<=sl.length;i++){sl.key[i]=rand();}}voidInsertSort(SqList&L){//对顺序表L作直接插入排序for(inti=2;i<=L.length;i++)if(L.key[i]<=L.key[i-1])//"<"需将L.key[i]插入有序子表{L.key[0]=L.key[i];//复制为哨兵L.key[i]=L.k

3、ey[i-1];for(intj=i-2;L.key[0]<=L.key[j];--j)L.key[j+1]=L.key[j];//记录后移L.key[j+1]=L.key[0];//插入到正确位置}}intmain(void){SqListsl;CreateSqList(sl);DWORDstart_time=GetTickCount();{InsertSort(sl);}DWORDend_time=GetTickCount();cout<<"直接插入排序时间为:"<<(end_time-start_time)<<"m

4、s!"<#include#include#include"assert.h"usingnamespacestd;structSqList{int*key;intlength;};voidCreateSqList(SqList&sl){srand((unsigned)time(NULL));//srand()函数产生一个以当前

5、时间开始的随机种子sl.length=10000;sl.key=newint[sl.length+1];assert(sl.key);for(inti=1;i<=sl.length;i++){sl.key[i]=rand();}}voidMerge(int*SR,int*TR,inti,intm,intn){//将有序的SR[i...m]和SR[m+1...n]归并为有序的TR[i...n]for(intj=m+1,k=i;i<=m&&j<=n;k++)//将SR中的记录由大到小并入TR{if(SR[i]<=SR[j])

6、TR[k]=SR[i++];elseTR[k]=SR[j++];}if(i<=m)//将剩余的SR[i...m]赋值到TRfor(inta=i;a<=m;a++)TR[k++]=SR[a];elseif(j<=n)//将剩余的SR[j...n]复制到TRfor(intb=j;b<=n;b++)TR[k++]=SR[b];}voidMSort(int*SR,int*TR1,ints,intt){intTR2[10001];//数组大小可以根据实际情况重新定义intm;//将SR[s...t]归并排序为TR[s...t]if

7、(s==t)TR1[s]=SR[s];else{m=(s+t)/2;//将SR[s...t]平分为SR[s...m]和SR[m+1...t]MSort(SR,TR2,s,m);//递归地将SR[s...m]归并为有序的TR2[s...m]MSort(SR,TR2,m+1,t);//递归地将SR[m+1...t]归并为TR2[m+1...t]Merge(TR2,TR1,s,m,t);//将TR2[s...m]和TR2[m+1...t]归并到TR1[s...t]}}voidMergeSort(SqList&L){//对顺序表

8、L作归并排序MSort(L.key,L.key,1,L.length);}intmain(void){SqListsl;CreateSqList(sl);DWORDstart_time=GetTickCount();{MergeSort(sl);}DWORDend_time=GetTickCount();cout<<