排序综合实验

实验名称：排序综合实验实验目的：参照各种排序算法程序样例，验证给出的排序常见算法。实验内容：输入一组关键字序列分别实现下列排序:实现简单选择排序、直接插入排序和冒泡排序。实现希尔排序算法。实现快速排序算法（取第一个记录或中间记录作为基准记录）。快速排序的非递归算法。实验要求：掌握各种排序算法的特点，测试并验证排序的常见算法。提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。实验原理直接插入排序：在线性表中只包含第一个元素的子表显然可以看成是有序表，接下来的问题是，从线性表的第二个元素开始直到最后一个元素，逐次将其中的每一个元素插入到前面已经有序的子表中。一般来说，假设线性表中前j-1个元素已经有序，将第j个元素插入到前面的有序子表的方法是：首先将第j个元素放到一个变量T中，然后从有序子表的最后一个元素开始逐个与T比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止，此时就将T插入到刚移出的空位置上，有序子表的长度就变为j了。冒泡排序：首先从表头开始往后扫描线性表，在扫描过程中逐次比较两个相邻元素的大小，若前面的元素大于后面的则互换，，最后将最大的元素移到了最后，然后从后到前扫描剩下的线性表，同样扫描过程中逐次比较相邻两个元素的大小，若后面的元素小于前面的，则互换，最后将最小的元素移到了最前面，对剩下的线性表重复上面的过程，直到剩下的表为空，线性表有序。快速排序：从线性表中选取一个元素T,然后将线性表后面小于T的元素移到前面，而大于T的元素移到后面，结果就将线性表分成了两部分（称为两个字表），T插入到分界线的位置处，如果对分割后的各子表再按上述原则将进行分割，直到所有子表为空为止，线性表有序。堆排序：首先将一个无序序列建成堆，然后将堆顶元素(序列中的最大项)与堆中最后一个元素交换，不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序列，显然该序列已不是堆，但左右子树仍为堆，可以将该子序列调整为堆，重复操作，直到剩下的子序列为空为止。实验步骤：通过主函数选择控制分别采用直接插入排序法、冒泡排序法、快速排序算法、快速排序的非递归算法、堆排序法实现给该组数据排序。实验结果：#include<iostream>#include<iomanip>usingnamespacestd;//冒泡排序template<classT>voidbub(Tp[],intn){intm,k,j,i;Td;k=0;m=n-1;while(k<m){j=m-1;m=0;for(i=k;i<=j;i++)if(p[i]>p[i+1]){d=p[i];p[i]=p[i+1];p[i+1]=d;m=i;}j=k+1;k=0;for(i=m;i>=j;i--)if(p[i-1]>p[i]){d=p[i];p[i]=p[i-1];p[i-1]=d;k=i;}}return;}//快速排序template<classT>voidqck(Tp[],intn)intm,i;T*s;if(n>10){i=split(p,n);qck(p,i);s=p+(i+1);m=n-(i+1);qck(s,m);}elsebub(p,n);return;}//表的分割template<classT>staticintsplit(Tp[],intn){inti,j,k,l;Tt;i=0;j=n-1;k=(i+j)/2;if((p[i]>=p[j])&&(p[j]>=p[k]))l=k;elseif((p[i]>=p[k])&&(p[k]>=p[j]))l=k;elsel=i;t=p[l];p[l]=p[i];while(i!=j){while((i<j)&&(p[j]>=t))j=j-1;if(i<j){p[i]=p[j];i=i+1;while((i<j)&&(p[i]<=t))i=i+1;if(i<j){p[j]=p[i];j=j-1;}}}p[i]=t;return(i);}//插入排序template<classT>voidinsort(Tp[],intn){intj,k;Tt;for(j=1;j<n;j++){t=p[j];k=j-1;while((k>=0)&&(p[k]>t)){p[k+1]=p[k];k=k-1;}p[k+1]=t;}return;}//希尔排序template<classT>voidshel(Tp[],intn){inti,k,j;Tt;k=n/2;while(k>0){for(j=k;j<=n-1;j++){t=p[j];i=j-k;while((i>=0)&&(p[i]>t)){p[j+k]=p[i];i=i-k;}p[i+k]=t;}k=k/2;}return;}//选择排序template<classT>voidselect(Tp[],intn){inti,j,k;Td;for(i=0;i<n-1;i++){k=i;for(j=i+1;j<n;j++)if(p[j]<p[k])k=j;if(k!=j){d=p[i];p[i]=p[k];p[k]=d;}}return;}template<classT>voidhap(Tp[],intn){inti,mm;Tt;mm=n/2;for(i=mm-1;i>=0;i--)sift(p,i,n-1);for(i=n-1;i>=1;i--){t=p[0];p[0]=p[i];p[i]=t;sift(p,0,i-1);}return;}intmain(){inti,j;doublep1[10]={4,3,2,1,5,7,6,8,9,0};doublep2[10]={4,3,2,1,5,7,6,8,9,0};doublep3[10]={4,3,2,1,5,7,6,8,9,0};doublep4[10]={4,3,2,1,5,7,6,8,9,0};doublep5[10]={4,3,2,1,5,7,6,8,9,0};cout<<"冒泡排序前的序列:"<<endl;for(i=0;i<1;i++){for(j=0;j<10;j++)cout<<setw(5)<<p1[10*i+j];cout<<endl;}bub(p1,10);cout<<"冒泡排序后的序列："<<endl;for(i=0;i<1;i++){for(j=0;j<10;j++)cout<<setw(5)<<p1[10*i+j];cout<<endl;}cout<<"快速排序前的序列:"<<endl;for(i=0;i<1;i++){for(j=0;j<10;j++)cout<<setw(5)<<p2[10*i+j];cout<<endl;}qck(p2,10);cout<<"快速排序后的序列:"<<endl;for(i=0;i<1;i++){for(j=0;j<10;j++)cout<<setw(5)<<p2[10*i+j];cout<<endl;}cout<<"插入排序前的序列:"<<endl;for(i=0;i<1;i++){for(j=0;j<10;j++)cout<<setw(5)<<p3[10*i+j];cout<<endl;}insort(p3,10);cout<<"插入排序后的序列:"<<endl;for(i=0;i<1;i++){for(j=0;j<10;j++)cout<<setw(5)<<p3[10*i+j];cout<<endl;}cout<<"希尔排序前的序列:"<<endl;for(i=0;i<1;i++){for(j=0;j<10;j++)cout<<setw(5)<<p4[10*i+j];cout<<endl;}shel(p4,10);cout<<"希尔排序后的序列:"<<endl;for(i=0;i<1;i++){for(j=0;j<10;j++)cout<<setw(5)<<p4[10*i+j];cout<<endl;}cout<<"选择排序前的序列:"<<endl;for(i=0;i<1;i++){for(j=0