内排序实验报告

地环院09级地信班实验报告学号：2011年1月7日院系地环学院班级课程名称数据结构姓名同组者无实验名称排序过程实验目的和要求：掌握几种有用的排序方法。希尔排序希尔排序通俗理解起来就一句话，每隔几个数字取两个数，并按你期望的大小把他们交换了。其原理就是使得一个无序的数组里，逐渐产生一小片一小片有序的序列，到最后，把这些有序的序列再拼接到一起，从而完成了整个无序到有序的排序过程。以下面的一组数据为例来加以验证012345678956277089732023564813下面的程序就是一个简单测试希尔排序的程序。具体程序见1.c#include<stdio.h>voidssort(intA[],intn,intsp)//简单的判断每隔sp个数就进行交换{ inti,j,t; for(i=0;i<n-sp;i++)//注意i的取值范围n-sp for(j=i;j<n-sp;j++) if(A[j]>A[j+sp]) { t=A[j];A[j]=A[j+sp];A[j+sp]=t;//交换程序 }}main(){ inta[]={56,27,70,89,73,20,23,56,48,13},n=10,sp=5; inti,j,t; for(i=0;i<n-sp;i++) for(j=i;j<n-sp;j+=sp) if(a[j]>a[j+sp]) { t=a[j];a[j]=a[j+sp]; a[j+sp]=t; } for(j=0;j<n;j++) printf("%4d",a[j]); printf("\n");//下面三句代码分别为隔5个、3个、1个进行交换，不管怎么样，最后必须为1 ssort(a,10,5); ssort(a,10,3); ssort(a,10,1); for(i=0;i<10;i++) printf("%4d",a[i]); printf("\n");}上面的程序代码直接写在了main()函数中，所以为了方便以后引用，我们做出修改完善的程序见2.c#include<stdio.h>voidssort(intA[],intn,intsp){ inti,j,t; for(i=0;i<n-sp;i++) for(j=i;j<n-sp;j++) if(A[j]>A[j+sp]) { t=A[j];A[j]=A[j+sp];A[j+sp]=t; }}voidshellsort(intA[],intn,intD[],intNumD)//希尔排序的程序，注意该函数中的几个参数{ inti; for(i=0;i<NumD;i++) ssort(A,n,D[i]);}main(){ inta[]={56,27,70,89,73,20,23,56,48,13},i,D[]={5,3,1}; shellsort(a,10,D,3);//引用希尔排序 for(i=0;i<10;i++) printf("%4d",a[i]); printf("\n");}到此为止，希尔排序完成。归并排序#include<stdio.h>#include<stdlib.h>voidmerge(intA[],intC[],intL,intM,intR)//数组A装的是需要排序的数据，数组C是辅助存储空间，L是数组A的左下标，R是数组A的右下标，M是介于L和R之间的数。{ inti,j,k;//申请三个整型变量。 for(i=L;i<=M;i++)//将数组A中从第一个数到第M个数装入到数组C中，此时数组C中有M个数据。 C[i]=A[i]; j=R;//给j赋初值。 for(i=M+1;i<=R;i++)//在数组A中的第m+1个数到最后一个数依次赋给C数组中的第M个数以后。 C[i]=A[j--]; i=L;j=R;//重新给i,j赋值。 for(k=L;k<=R;k++)//k的取值范围为C数组中的最小的下标到最大下标志。 A[k]=(C[i]<C[j])?C[i++]:C[j--];//把数组C中的数据从第一个和最后一个比较。}1234567891023114566733221589456数组ALvoidMSort(intA[],intC[],intL,intR)//将数组C划分为若干部分进行排序。{ intM;//申请一个整型变量。 M=(L+R)/2;//M为数组A的中间下标值。 if(R<=L)return;//如果右下标小于左下标，则直接退出。 MSort(A,C,L,M);//用递归对数组A的左半部分排序。 MSort(A,C,M+1,R);//用递归对数组A的右半部分排序。 merge(A,C,L,M,R);//以数组的中间下标分成两部分分别排序。}voidmergesort(intA[],intn)//对数组A进行排序。{ int*C;//构造辅助存储数组C。 C=(int*)malloc(sizeof(int)*n);//为数组A申请存储空间。 MSort(A,C,0,n-1);//调用排序函数。 free(C);//释放存储空间C。}main(){ intA[]={0}; scanf("%d",&A[i]);mergesort(A,n); for(i=0;i<n;i++) printf("%d\t",A[i]); printf("\n");}快速排序以下快速排序的图解说明排序的原理：快速排序示意图#include<stdio.h>voidQsort(intA[],intlow,inthigh)//快速排序，low是数组A的最小下标，high是最大下标值{ inti,j,p;//i,j控制循环，p存储支点 i=low;j=high; if(i>=j)return;//递归返回的条件 p=A[i];//将A[i]给p作为支点 while(i<j)//一趟排序 { while(i<j&&A[j]>=p)//当从右往左走时，A[j]大于支点值时，一直往左走，否则，退出循环 j--; if(i<j)//当A[j]小于支点值时 { A[i]=A[j];//将A[j]给A[i],也就是移到左侧 i++;//i加1，即i右移 } while(i<j&&A[i]<p)//当从左往右走时，A[i]小于于支点值时，一直往右走，否则，退出循环 i++; if(i<j)//当A[i]大于支点值时 { A[j]=A[i];//将A[i]给A[j],也就是移到右侧 j--;//j减1，即j向左移 } } A[i]=p;//将支点给A[i] Qsort(A,low,i-1);//支点左侧再做快速排序 Qsort(A,i+1,high);//支点右侧再做快速排序}main(){ intA[6]={30,10,4,9,5,20}; inti; Qsort(A,0,5); printf("排序结果是：\n"); for(i=0;i<6;i++) printf("%4d",A[i]); printf("\n");}基数排序#include<stdio.h>#include<stdlib.h>voidJishuSort(intA[],intn)//基数排序{ int*C;//说明一指针C,用来构造动态数组 inti,m,max=A[0],t=0; for(i=0;i<n;i++) if(max<A[i])//求数组A中的最大值，用来申请C数组所占的存储空间 max=A[i]; max++;//最大值++ C=(int*)malloc(sizeof(int)*max);//给数组C申请存储空间 for(i=0;i<max;i++) C[i]=0;//初始化数组C for(i=0;i<n;i++) { m=A[i];//将数组A的值给m C[m]=1;//将数组C中以数组A中的值为下标的值赋予1 } for(m=0;m<max;m++) if(C[m]!=0)//判断C数组中值是否为0 A[t++]=m;//如不为0，则装入A中，并且A中数组的下标是从0开始的}main(){ intA[]={22,3,45,67,21,23}; inti; JishuSort(A,6); printf("排序结果是：\n"); for(i=0;i<6;i++) printf("%4d",A[i]);//打印排序后的数组 printf("\n");}堆排序堆排序的原理是按给出的数据构造成二叉树，再找出第一个最大数，把这个最大数去掉后，再在其他的数据中找出最大数，依次照完所有的数。#include<stdio.h>voidHeadAdjust(inta[],ints,intn)//调整二叉树使其变为大顶堆。{ inti,t;//申请两个整型变量。 while(2*s+1<n)//如果二叉树中第S个结点的左孩子标号小于n。 { i=2*s+1;//将标号附为i。 if((i+1)<n)//如果二叉树中第S个结点的右孩子标号小于n。 { if(a[i]<a[i+1])i++;//将二叉树的左右孩子结点值调换。 } if(a[s]<a[i])//如果二叉树中第S个结点的结点值小于右孩子结点值，将他们两结点值调换。。 { t=a[s]; a[s]=a[i]; a[i]=t; s=i; } else break; }}voidHeadSort(intA[],intn)//构造函数检查每一个结点。voidHeadSort(intA[],intn)//构造函数检查每一个结点。{ inti,t; for(i=n/2-1;i>=0;i--) HeadAdjust(A,i,n);//调用上面的函数测试其中的结点。 for(i=n-1;i>=0;i--)//对剩下的其他节点再进行调整。 { t=A[0]; A[0]=A[i]; A[i]=t; HeadAdjust(A,0,i); }}这里二叉树如下，它的过程是通过调整二叉树先找出这些数中的第一个最大值在从剩下的数中找出最大值，依次直到这些数据找完。第一步调整。main(){ inti,A[]={12,34,45,56,3,2,45,66,67,43}; HeadSort(A,10); for(i=0;i<10;i++) printf("%d",A[i]); printf("\n"); /*inti,A[]={0},n; printf("请输入要排序的数据个数n\n"); scanf("%d",&n); printf("请输入要排序的数据\n")