排序算法课程设计

排序算法课程设计专业班级学号姓名指导老师一：课程设计的目的1.掌握各种排序的基本思想2.掌握各种排序的算法实现3.掌握各种排序的算法优劣分析花费的时间计算4.掌握各种排序算法所适用的不同场合。二：课程设计的内容（1）冒泡、直插、选择、快速、希尔、归并、堆排序算法进行比较；（2）待排序的元素的关键字为整数。其中的数据用伪随机产生程序产生（如10000个,1000个），再使用各种算法对其进行排序，记录其排序时间，再汇总比较；（3）将每次测试所用的时间，用条形图进行表示，以便比较各种排序的优劣。三：课程设计的实现（1）直接插入排序#includeiostream.htypedefintkeytype;structdatatype{keytypekey;};/*intrand(void);voidsrand(unsignedintseed);*/#includestdlib.h#includestdio.h#includetime.h#includewindows.hvoidInsertSort(datatypea[],intn)//用直接插入法对a[0]--a[n-1]排序{inti,j;datatypetemp;for(i=0;in-1;i++){temp=a[i+1];j=i;while(j-1&&temp.key=a[j].key){a[j+1]=a[j];j--;}a[j+1]=temp;}}voidmain(){/*srand((unsigned)time(NULL));//随机种子*//*time_tt;srand((unsigned)time(&t));*/time_tt1,t2;srand((unsigned)GetCurrentTime());datatypenum[10000];t1=GetCurrentTime();for(inti=0;i10000;i++){num[i].key=rand();}intn=10000;InsertSort(num,n);for(intj=0;j10000;j++)coutnum[j].keyendl;t2=GetCurrentTime();coutThet1timeis:t1Thet2timeis:t2t2-t1:t2-t1endl;getchar();}（2）希尔排序#includeiostream.h/*intrand(void);voidsrand(unsignedintseed);*/#includestdlib.h#includestdio.h#includetime.h#includewindows.htypedefintkeytype;structdatatype{keytypekey;};voidShellSort(datatypea[],intn,intd[],intnumOfD)//用希尔排序法对记录a[0]--a[n-1]排序//各组内采用直接插入法排序{inti,j,k,m,span;datatypetemp;for(m=0;mnumOfD;m++){span=d[m];for(k=0;kspan;k++){for(i=k;in-span;i=i+span){temp=a[i+span];j=i;while(j-1&&temp.key=a[j].key){a[j+span]=a[j];j=j-span;}a[j+span]=temp;}}}}voidmain(){/*srand((unsigned)time(NULL));//随机种子*//*time_tt;srand((unsigned)time(&t));*/time_tt1,t2;srand((unsigned)GetCurrentTime());datatypenum[10000];t1=GetCurrentTime();for(inti=0;i10000;i++){num[i].key=rand();}intn=10000,d[]={1000,100,10,1},numOfd=4;ShellSort(num,n,d,numOfd);for(intj=0;j10000;j++)coutnum[j].keyendl;t2=GetCurrentTime();coutThet1timeis:t1Thet2timeis:t2t2-t1:t2-t1endl;getchar();}（3）直接选择排序#includeiostream.htypedefintkeytype;structdatatype{keytypekey;};/*intrand(void);voidsrand(unsignedintseed);*/#includestdlib.h#includestdio.h#includetime.h#includewindows.hvoidSelectSort(datatypea[],intn)/*用直接选择排序法对a[0]--a[n-1]排序*/{inti,j,s;datatypetemp;for(i=0;in-1;i++){s=i;for(j=i+1;jn;j++)if(a[j].keya[s].key)s=j;if(s!=i){temp=a[i];a[i]=a[s];a[s]=temp;}}}voidmain(){/*srand((unsigned)time(NULL));//随机种子*//*time_tt;srand((unsigned)time(&t));*/time_tt1,t2;srand((unsigned)GetCurrentTime());datatypenum[10000];t1=GetCurrentTime();for(inti=0;i10000;i++){num[i].key=rand();}intn=10000;SelectSort(num,n);for(intj=0;j10000;j++)coutnum[j].keyendl;t2=GetCurrentTime();coutThet1timeis:t1Thet2timeis:t2t2-t1:t2-t1endl;getchar();}（4）堆排序#includeiostream.htypedefintkeytype;structdatatype{keytypekey;};#includestdlib.h#includestdio.h#includetime.h#includewindows.hvoidCreatHeap(datatypea[],intn,inth){inti,j,flag;datatypetemp;i=h;//i为要建堆的二叉树根结点下标j=2*i+1;//j为i的左孩子结点的下标temp=a[i];flag=0;//沿左右孩子中值较大者重复向下筛选while(jn&&flag!=1){//寻找左右孩子结点中的较大者,j为其下标if(jn-1&&a[j].keya[j+1].key)j++;if(temp.keya[j].key)//a[i].keya[j].keyflag=1;//标记结束筛选条件else//否则把a[j]上移{a[i]=a[j];i=j;j=2*i+1;}}a[i]=temp;//把最初的a[i]赋予最后的a[j]}voidInitCreatHeap(datatypea[],intn){inti;for(i=(n-1)/2;i=0;i--)CreatHeap(a,n,i);}voidHeapSort(datatypea[],intn){inti;datatypetemp;InitCreatHeap(a,n);//初始化创建最大堆for(i=n-1;i0;i--)//当前最大堆个数每次递减1{//把堆顶a[0]元素和当前最大堆的最后一个元素交换temp=a[0];a[0]=a[i];a[i]=temp;CreatHeap(a,i,0);//调整根结点满足最大堆}}voidmain(){/*srand((unsigned)time(NULL));//随机种子*//*time_tt;srand((unsigned)time(&t));*/time_tt1,t2;srand((unsigned)GetCurrentTime());datatypenum[10000];t1=GetCurrentTime();for(inti=0;i10000;i++){num[i].key=rand();}intn=10000;HeapSort(num,n);for(intj=0;j10000;j++)coutnum[j].keyendl;t2=GetCurrentTime();coutThet1timeis:t1Thet2timeis:t2t2-t1:t2-t1endl;getchar();}（5）冒泡排序#includeiostream.htypedefintkeytype;structdatatype{keytypekey;};#includestdlib.h#includestdio.h#includetime.h#includewindows.hvoidBubbleSort(datatypea[],intn)//用冒泡排序法对a[0]--a[n-1]排序{inti,j,flag=1;datatypetemp;for(i=1;in&&flag==1;i++){flag=0;for(j=0;jn-i;j++){if(a[j].keya[j+1].key){flag=1;temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}}voidmain(){/*srand((unsigned)time(NULL));//随机种子*//*time_tt;srand((unsigned)time(&t));*/time_tt1,t2;srand((unsigned)GetCurrentTime());datatypenum[10000];t1=GetCurrentTime();for(inti=0;i10000;i++){num[i].key=rand();}intn=10000;BubbleSort(num,n);for(intj=0;j10000;j++)coutnum[j].keyendl;t2=GetCurrentTime();coutThet1timeis:t1Thet2timeis:t2t2-t1:t2-t1endl;getchar();}（6）快速排序#includeiostream.h/*intrand(void);voidsrand(unsignedintseed);*/#includestdlib.h#includestdio.h#includetime.h#includewindows.htypedefintkeytype;structdatatype{keytypekey;};voidQuickSort(datatypea[],intlow,inthigh)//用递归方法对对象a[low]--a[high]进行快速排序{inti,j;datatypetemp;i=low;j=high;temp=a[low];while(ij){//在数组的右端扫描while(ij&&temp.key=a[j].key)j--;if(ij){a[i]=a[j];i++;}//在数组的左端扫描while(ij&&a[i].keytemp.key)i++;if(ij){a[j]=a[i];j--;}}a[i]=temp;