课程设计报告数据结构课程设计题目：各种排序*******专业：网络工程班级：10211302学号：**********指导教师：姜林王志波2012年6 月27 日目录排序算法比较一、程序要求分析二、程序主要功能三、程序运行平台四、程序数据结构五、算法及时间复杂度六、程序源代码七、自我总结各种排序一、需求分析任务：用程序实现插入法排序、起泡法、选择法、快速法、合并法排序；输入的数据形式为任何一个正整数，大小不限。
输出的形式：数字大小逐个递增的数列。
要求给出多组不同元素个数的输入数据，并用列表打印出每种排序下的各趟排序结果。
每个排序法结束时应打印出其元素比较的次数和交换的次数。
此程序需将结果用列表打印，一定要将其打印结果排列好。
二、程序的主要功能1.用户输入任意个数，产生相应数量的随机数2.用户可以自己选择排序方式（直接插入排序，冒泡排序、快速排序、选择排序、二路归并排序五种排序方法）的一种3.程序给出原始数据、排序后从小到大的数据，并给出排序所用的时间，比较的总次数和交换的总次数。
三、程序运行平台Visual C++ 6.0版本四、数据结构1.类：NuovSort{public:void Myface();void choose();void insertsort(int R[],int n); //直接插入排序法void Bubblesort(int R[],int n); //冒泡排序算法实现void quicksort(int R[],int left,int right); //快速排序算法实现void selectsort(int R[],int n); //直接选择排序算法实现void merge(int R[],int A[],int s,int m,int t);//二路归并排序算法实现void mergepass(int R[],int A[],int n,int c);void mergesort(int R[],int n);};2.主界面：Myface() //界面{cout<<"\t -->各种排序算法实现<--"<<endl;cout<<"#^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^#"<<endl;cout<<"# 1.直接插入排序#"<<endl;cout<<"# 2.冒泡排序#"<<endl;cout<<"# 3.快速排序#"<<endl;cout<<"# 4.直接选择排序#"<<endl;cout<<"# 5.二路归并排序#"<<endl;cout<<"#^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^#"<<endl;cout<<"enter your choose:";}3.选择界面：choose(){int i,x,n,s,t;time_t t1,t2;double tt1,tt2,tt3,tt4,tt5;cout<<"\t\t\t 欢迎您使用高扬的排序程序"<<endl;cout<<"请问，需要几个被排序数字？"<<endl;do{cout<<"请输入个数(范围在1~500 之间): ";cin>>n;}while((n<1)||(n>500));int left=0,right=n-1;for(i=0;i<n;i++)R[i]=rand()%888+1; //产生随机数cout<<"被排序的数字随机产生如下："<<endl;for(i=0;i<n;i++)cout<<R[i]<<" ";cout<<endl;cout<<endl;Myface();int m=0;cin>>m;switch(m){case 1:t1=time(NULL);insertsort(R,n);t2=time(NULL);tt1=difftime(t2,t1);cout<<"排序所需时间为："<<tt1<<endl;break; //直接插入排序算法实现case 2:t1=time(NULL);Bubblesort(R,n);t2=time(NULL);tt2=difftime(t2,t1);cout<<"排序所需时间为："<<tt2<<endl;break; //冒泡排序算法实现case 3:t1=time(NULL);cout<<"Before the sort,your answer is:";for(x=0;x<n;x++){cout.width(4);cout<<R[x]<<" ";}cout<<endl;quicksort(R,left,right);cout<<"排序的结果是：";for(x=0;x<n;x++)cout<<R[x]<<" ";cout<<endl;cout<<endl;cout<<"元素比较次数为"<<comN3<<"次"<<endl;cout<<"元素交换次数为"<<chaN3<<"次"<<endl;t2=time(NULL);tt3=difftime(t2,t1);cout<<"排序所需时间为："<<tt3<<endl;break; //快速排序算法实现case 4:t1=time(NULL);selectsort(R,n);t2=time(NULL);tt4=difftime(t2,t1);cout<<"排序所需时间为："<<tt4<<endl;break; //直接选择排序算法实现case 5:t1=time(NULL);mergesort(R,n);cout<<endl;cout<<"元素比较次数为"<<comN5<<"次"<<endl;cout<<"元素交换次数为"<<chaN5<<"次"<<endl;t2=time(NULL);tt5=difftime(t2,t1);cout<<"排序所需时间为："<<tt5<<endl;break; //二路归并排序算法实现default:cout<<"input error "<<endl;choose();}}五、算法及时间复杂度（一）各个排序的算法思想：（1）直接插入排序算法思想：将一个记录插入到已排好的有序表中，从而得到一个新的，记录数增加1的有序表。
（2）起泡排序算法思想：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。
依此类推，直到第N-1和第N个记录的关键字进行过比较为止。
上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。
然后进行第二趟起泡排序，对前N-1个记录进行同样操作。
一共要进行N-1趟起泡排序。
（3）快速排序算法思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。
（4）选择排序算法思想：通过N-I次关键字间的比较，从N-I+1个记录中选出关键字最小的记录，并和第I（1<=I<=N）个记录交换。
（5）二路归并排序算法思想：先将每个数确定为一个空间，然后两两比较，把排序后的结果放在新数组中，然后再两两比较，以此类推，最终把所有的子区间合并为一个区间。
（二）时间复杂度分析六、程序源代码/**********************************************************************************************设计要求：利用随机函数产生N个随机整数（N = 1到500），利用直接插入排序，冒泡排序、快速排序、选择排序、二路归并排序五种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间，比较的总次数和交换的总次数。
#include<ctime>#include<math.h>#include<stdlib.h>#include<iostream>#include<time.h>using namespace std;const int maxsize=500;int R[maxsize];int A[maxsize];int i,n,right,left;int comN1=0,chaN1=0; //直接插入排序中元素比较的次数和交换的次数int comN2=0,chaN2=0; //冒泡排序中元素比较的次数和交换的次数int comN3=0,chaN3=0; //快速排序中元素比较的次数和交换的次数int comN4=0,chaN4=0; //直接选择排序中元素比较的次数和交换的次数int comN5=0,chaN5=0; //合并排序中元素比较的次数和交换的次数class NuovSort{public:void Myface();void choose();void insertsort(int R[],int n); //直接插入排序法void Bubblesort(int R[],int n); //冒泡排序算法实现void quicksort(int R[],int left,int right); //快速排序算法实现void selectsort(int R[],int n); //直接选择排序算法实现void merge(int R[],int A[],int s,int m,int t);//二路归并排序算法实现void mergepass(int R[],int A[],int n,int c);void mergesort(int R[],int n);};void NuovSort::Myface() //界面{cout<<"\t -->各种排序算法实现<--"<<endl;cout<<"#^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^#"<<endl;cout<<"# 1.直接插入排序#"<<endl;cout<<"# 2.冒泡排序#"<<endl;cout<<"# 3.快速排序#"<<endl;cout<<"# 4.直接选择排序#"<<endl;cout<<"# 5.二路归并排序#"<<endl;cout<<"#^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^#"<<endl;cout<<"enter your choose:";}void Display(int R[], int n){for(int i=0;i<n;i++){cout.width(4);cout<<R[i];}cout<<endl<<endl;}void NuovSort::choose(){int i,x,n,s,t;time_t t1,t2;double tt1,tt2,tt3,tt4,tt5;cout<<"\t\t\t 欢迎您使用高扬的排序程序"<<endl;cout<<"请问，需要几个被排序数字？"<<endl;do{cout<<"请输入个数(范围在1~500 之间): ";cin>>n;}while((n<1)||(n>500));int left=0,right=n-1;for(i=0;i<n;i++)R[i]=rand()%888+1; //产生随机数cout<<"被排序的数字随机产生如下："<<endl;for(i=0;i<n;i++)cout<<R[i]<<" ";cout<<endl;cout<<endl;Myface();int m=0;cin>>m;switch(m){case 1:t1=time(NULL);insertsort(R,n);t2=time(NULL);tt1=difftime(t2,t1);cout<<"排序所需时间为："<<tt1<<endl;break; //直接插入排序算法实现case 2:t1=time(NULL);Bubblesort(R,n);t2=time(NULL);tt2=difftime(t2,t1);cout<<"排序所需时间为："<<tt2<<endl;break; //冒泡排序算法实现case 3:t1=time(NULL);cout<<"Before the sort,your answer is:";for(x=0;x<n;x++){cout.width(4);cout<<R[x]<<" ";}cout<<endl;quicksort(R,left,right);cout<<"排序的结果是：";for(x=0;x<n;x++)cout<<R[x]<<" ";cout<<endl;cout<<endl;cout<<"元素比较次数为"<<comN3<<"次"<<endl;cout<<"元素交换次数为"<<chaN3<<"次"<<endl;t2=time(NULL);tt3=difftime(t2,t1);cout<<"排序所需时间为："<<tt3<<endl;break; //快速排序算法实现case 4:t1=time(NULL);selectsort(R,n);t2=time(NULL);tt4=difftime(t2,t1);cout<<"排序所需时间为："<<tt4<<endl;break; //直接选择排序算法实现case 5:t1=time(NULL);mergesort(R,n);cout<<endl;cout<<"元素比较次数为"<<comN5<<"次"<<endl;cout<<"元素交换次数为"<<chaN5<<"次"<<endl;t2=time(NULL);tt5=difftime(t2,t1);cout<<"排序所需时间为："<<tt5<<endl;break; //二路归并排序算法实现default:cout<<"input error "<<endl;choose();}}//直接插入排序算法实现void NuovSort::insertsort(int R[],int n){int p,x=1;for(int i=1;i<n;i++){int temp=R[i];int j=i-1;while((j>=0)&&(temp<R[j])){comN1++;R[j+1]=R[j];j--;}comN1++;R[j+1]=temp;chaN1++;cout<<"第"<<x++<<"趟被排序的数字如下："<<endl;for(p=0;p<n;p++){cout.width(4);cout<<R[p]<<" ";}cout<<endl;}cout<<endl;cout<<"元素比较次数为"<<comN1<<"次"<<endl;cout<<"元素交换次数为"<<chaN1<<"次"<<endl;}//冒泡排序算法实现void NuovSort::Bubblesort(int R[],int n){int flag=1;int x=1; //当flag为0时则停止排序for(int i=1;i<n;i++){for(int i=1;i<n;i++){//i表示趟数，最多n-1趟flag=0;for(int j=n-1;j>=i;j--){comN2++;if(R[j]<R[j-1]){//发生逆序int t=R[j];R[j]=R[j-1];R[j-1]=t;flag=1;//交换，并标记发生了变化chaN2++;}}cout<<"第"<<x++<<"趟被排序的数字如下："<<endl;for(i=0;i<n;i++){cout.width(4);cout<<R[i];}cout<<endl;}if(flag==0)break;}cout<<endl;cout<<"元素比较次数为"<<comN2<<"次"<<endl;cout<<"元素交换次数为"<<chaN2<<"次"<<endl;}//快速排序算法实现void NuovSort::quicksort(int R[],int left,int right) {int k=left,j=right;int n=right;int t,temp=R[k];while(k<j){while((R[j]>temp)&&(j>k)){comN3++;j--;}if(k<j){t=R[k];R[k]=R[j];R[j]=t;chaN3++;k++;}while((R[k]<temp)&&(k<j)){comN3++;k++;}if(k<j){t=R[k];R[k]=R[j];R[j]=t;chaN3++;j--;}}//一次划分得到基准值的正确位置R[k]=temp;if(left<k-1)quicksort(R,left,k-1);if(k+1<right)quicksort(R,k+1,right);}//直接选择排序算法实现void NuovSort::selectsort(int R[],int n){int i,j,m,p;int t;for(i=0;i<n-1;i++){m=i;for(j=i+1;j<n;j++)if(R[j]<R[m]){comN4++;m=j;}if(m!=i){t=R[i];R[i]=R[m];R[m]=t;chaN4++;}cout<<"第"<<i+1<<"趟被排序的数字如下："<<endl;for(p=0;p<n;p++){cout.width(4);cout<<R[p]<<" ";}cout<<endl;}cout<<endl;cout<<"元素比较次数为"<<comN4<<"次"<<endl;cout<<"元素交换次数为"<<chaN4<<"次"<<endl;}//二路归并排序算法实现void NuovSort::merge(int R[],int A[],int s,int m,int t)//将两个子区间R[s]~R[m]和R[m+1]~R[t]合并，结果存储在A中{int i,j,temp;i=s;j=m+1;while((i<=m)&&(j<=t)){comN5++;if(R[i]>=R[j]){chaN5++;temp=R[j];for(int k=j-1;k>=i;k--){R[k+1]=R[k];}R[i]=temp;j++;}else{i++;}}for(int l=s;l<=t;l++)A[l]=R[l];}void NuovSort::mergepass(int R[],int A[],int n,int c)//对R数组做一趟排序归并，结果存入A数组中，n为元素个数，c为区间长度{int i,j;i=0;while(i+2*c-1<=n-1)//长度均为c的两个区间合并成一个区间{merge(R,A,i,i+c-1,i+2*c-1);i+=2*c;}if(i+c-1<n) //长度不等的两个区间合并成一个区间merge(R,A,i,i+c-1,n-1);else //仅剩一个区间时直接复制到A中for(j=i;j<=n-1;j++)A[j]=R[j];}void NuovSort::mergesort(int R[],int n){int c=1,i=0,k=1;int A[maxsize];cout<<"二路归并排序的每一次的结果如下："<<endl<<endl;cout<<"初始状态:";Display(R,n);while(c<n){mergepass(R,A,n,c); //一次合并且结果存入A中i=i+1;cout<<"第"<<k<<"趟: ";k++;Display(R,n);c*=2;mergepass(A,R,n,c); //再次合并且结果存入R中i=i+1;cout<<"第"<<k<<"趟: ";k++;Display(R,n);c*=2;}}//函数的实现int main(){NuovSort v;char ch;cout<<"\t\t\t -->各种排序算法实现<--"<<endl;do{v.choose();cout<<endl;cout<<"\t\t\t --> 继续操作按'Y;,退出按'N' <-"<<endl;cin>>ch;while(ch!='Y'&&ch!='N'){cout<<"请根据提示操作！## 继续操作按'Y;,退出按'N' ##"<<endl;cin>>ch;}}while(ch!='N');return 0;}七、自我总结经过三天的努力，终于做完了这份程序。
