内部排序

实内部排序一、实验目的1、掌握排序的有关概念和特点。2、熟练掌握直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序等算法的基本思想。。3、关键字序列有序与无序，对于不同的排序方法有不同的影响，通过该实验进一步加深理解。二、实验内容设有关键字序列k={12,45,21,12,30,2,68,33},试用各种排序算法进行排序。三、实验环境TC或VC++或Java四、实验步骤1、从键盘输入上述8个整数，存放在数组quick[8]中，并输出值。2、输出直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序算法每一趟排序的结果，观察关键字次序的变化。3、如果上述8个整数按照升序输入，即k1={2,12,12,21,30,33,45,68}，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。4、如果上述8个整数按照降序输入，即k2={68,45,33,30,21,12,12,2}，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。5、随机产生3万个数，对其进行排序，观察其结果，并测试各排序算法的执行时间，比较执行效率。五、问题讨论1、直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序中哪些是稳定的排序方法，哪些是不稳定的？2、直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序中哪些排序方法比较次数与初始序列有关，那些无关？3、在初始序列基本有序的前提条件下，哪种排序方法效率最高？六、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及相应的运行结果6、问题回答7、实验心得实验代码：以下为C++代码#includecmath#includetime.h#includestdio.h#includecstring#includestdlib.h#includeiostreamusingnamespacestd;#defineNUM100#defineM30000voidZhijiepaixu(int*pData,intn)//形参为输入的数据及输入数据的个数{//直接插入排序intiTemp;boolflag=1;intiPos;for(inti=1;in;i++){iTemp=pData[i];iPos=i-1;while((iPos=0)&&(iTemppData[iPos])){if(flag){flag=0;}pData[iPos+1]=pData[iPos];//将值大的数放在后面iPos--;}flag=1;pData[iPos+1]=iTemp;//因为iPos执行了一次--所以将第i个值赋给iPos+1}}voidXuanzepaixu(int*pData,intn){//选择排序intiTemp;intiPos;boolflag=1;for(inti=0;in-1;i++){iTemp=pData[i];iPos=i;for(intj=i+1;jn;j++){if(pData[j]iTemp)//如果第j个数小于第i个数则将第i个数赋值给此趟比较的最小值上{if(flag){flag=0;}iTemp=pData[j];iPos=j;}}pData[iPos]=pData[i];pData[i]=iTemp;}}voidQipaopaixu(int*pData,intn)//形参为输入的数据及输入数据的个数{//起泡排序intiTemp;boolflag=1;for(inti=1;in;i++){for(intj=n-1;j=i;j--){if(pData[j]pData[j-1]){if(flag){flag=0;}iTemp=pData[j-1];pData[j-1]=pData[j];pData[j]=iTemp;}}}}voidShellpaixu(int*pData,intn){//希尔排序intstep[6]={24,15,9,5,3,1};boolflag=1;inti,iTemp;intk,w;for(i=0;i6;i++){k=step[i];for(intj=k;jn;j++){iTemp=pData[j];w=j-k;//求上step个元素的下标while((iTemppData[w])&&(w=0)&&(w=n)){if(flag){flag=0;}pData[w+k]=pData[w];w=w-k;}pData[w+k]=iTemp;}}}voidrun(int*pData,intleft,intright){inti,j;intmiddle,iTemp;i=left;j=right;boolflag=1;middle=pData[(left+right)/2];//求中间值do{while((pData[i]middle)&&(iright))//从左扫描大于中值的数{i++;if(flag){flag=0;}}while((pData[j]middle)&&(jleft))//从右扫描大于中值的数{j--;if(flag){flag=0;}}if(i=j)//找到了一对值{//交换iTemp=pData[i];pData[i]=pData[j];pData[j]=iTemp;i++;j--;}}while(i=j);//如果两边扫描的下标交错，就停止（完成一次）//当左边部分有值(leftj)，递归左半边if(leftj)run(pData,left,j);//当右边部分有值(righti)，递归右半边if(righti)run(pData,i,right);}voidKuaisupaixu(int*pData,intn){//快速排序run(pData,0,n-1);}voidZhijiaohuan(int&a,int&b){//进行值的交换inttmp;tmp=a;a=b;b=tmp;}voidheap_adjust(intarray[],inti,intn){//实现子结点值大于父结点，且左子树值小于右子树intrc=array[i];for(intj=2*i;j=n;j*=2){if(jn&&array[j]array[j+1])j++;if(rc=array[j])break;array[i]=array[j];i=j;}array[i]=rc;}voidDuipaixu(int*pData,intn){inti;for(i=n/2;i0;i--)heap_adjust(pData,i,n);for(i=n;i1;i--){Zhijiaohuan(pData[1],pData[i]);//弹出最大值，重新对i-1个元素建堆heap_adjust(pData,1,i-1);}}intSort(inta[],intmerge[],intlow,inthigh)//把a中的值排序到merge中{intb[M];//这是个temp局部值，它能保存两个半区intmid=(high+low)/2;inti=low,j=mid+1,k=low;if(low=high)//递归出口{if(low==high)merge[low]=a[low];return0;}Sort(a,b,low,mid);//分成两个子数组，进行排序Sort(a,b,mid+1,high);while((i=mid)&&(j=high))//进行合并操作{if(b[i]=b[j]){merge[k++]=b[i++];}else{merge[k++]=b[j++];}}while(i=mid){merge[k++]=b[i++];}while(j=high){merge[k++]=b[j++];}return0;}intRADIX(intarray[],intp){intN[10],k=0;inti=0,n,a[10][10000],j,m=0;for(i=0;i10;i++)N[i]=0;for(i=0;ip;i++){n=array[i]/((int)pow(10,(double)k))%10;a[n][N[n]++]=array[i];}for(i=0;i10;i++)for(j=0;jN[i];j++)array[m++]=a[i][j];}intrandom(intA[]){inti;for(i=0;iM;i++)A[i]=rand()%30001;}voidShiJian(){intA[M],B[M+1],C[M],D[M],i,j;time_tstart1,end1,start2,end2,start3,end3,start4,end4;time_tstart5,end5,start6,end6,start7,end7,start8,end8;random(C);for(i=0;iM;i++)A[i]=C[i];start1=time(NULL);Zhijiepaixu(A,M);end1=time(NULL);cout直接排序的运行时间为:end1-start1秒!endl;for(i=0;iM;i++)A[i]=C[i];start2=time(NULL);Xuanzepaixu(A,M);end2=time(NULL);cout选择排序的运行时间为:end2-start2秒!endl;for(i=0;iM;i++)A[i]=C[i];start3=time(NULL);Qipaopaixu(A,M);end3=time(NULL);cout冒泡排序的运行时间为:end3-start3秒!endl;for(i=0;iM;i++)A[i]=C[i];start4=time(NULL);Shellpaixu(A,M);end4=time(NULL);cout希尔排序的运行时间为:end4-start4秒!endl;for(i=0;iM;i++)A[i]=C[i];start5=time(NULL);Kuaisupaixu(A,M);end5=time(NULL);cout快速排序的运行时间为:end5-start5秒!endl;for(i=0,j=1;iM,j=M;i++,j++)B[j]=C[i];start6=time(NULL);Duipaixu(B,M);end6=time(NULL);cout堆排序的运行时间为:end6-start6秒!endl;/*for(i=0;iM;i++)A[i]=C[i];start7=time(NULL);Sort(A,D,0,M-1);end7=time(NULL);cout归并排序的运行时间为:end7-start7秒!endl;*/for(i=0;iM;i++)A[i]=C[i];start8=time(NULL);for(i=0;i5;i++)RADIX(A,M);end8=time(NULL);cout基数排序的运行时间为:end8-start8秒!endl;}voidmenu1(){printf(-----------------------------------\n);printf(排序类型：\n);printf(1.直接插入排序\n);printf(2.直接选择排序\n);printf(3.起泡排序\n);printf(4.Shell排序\n);printf(5.快速快序\n);printf(6.堆排序\n);printf(7.归并排序\n);printf(8.基数排序\n);printf(0.结束排序\n);printf(------------------------