排序实验报告

数据结构实验报告排序小组成员：张家铭2010416648吴建明2010416603刘仕乾2010416682王战海2010416596

1实验题目为了更好的学习数据结构，理解排序思想，直观的观察出每一步所进行的操作。进行此实验报告。主要包含直接插入排序，希尔排序，冒泡排序，快速排序，选择排序，堆排序。2需求分析在现在的任何pc、mac上均可装有c-Free或VC6.0上均可编写调试。（1）输入形式，先用种子函数初始化随机生成函数，然后用随机生成函数生成十个数据。通过选择你想选用的排序方式包括：insertSort（arr,10）;//插入排序shellSort（arr,3,10）;//希尔排序bubbleSort（arr,10）;//冒泡排序QuickSort（arr,1,11）;//快速排序selectSort（arr,10）;//选择排序heapsort（arr,10000）;//堆排序（2）输出形式，通过调用printarr函数进行输出数据，并在排序之中调用此函数了来直观的查看排序的过程。（3）程序附加功能，在排序进行之前设计了开始时间（start=time（NLULL）），在排序结束之后设计了结束时间（end=time（NULL）），之后在输出该排序执行的时间（printf（"执行时间为：％d\n”,（end-start））;）。直观的看出该程序的优劣。PS：执行小量数据体现不出时间损耗，可以设计大量数据看出时间损耗。（4）测试数据，随机生成，数据不定。3概要设计包含的头文件#include<stdio.h>#include<stdlib.h>#include<time.h>用于生成随机函数和计时用本程序包含的主要函数：〃输出列表函数//插入排序注意监视哨作用//希尔排序一趟d为步长//希尔排序//冒泡排序〃快速排序重点的排序//选择排序//建堆i为根节点n为个数//堆排序//主函数voidprintarr(intarr[],intn)voidinsertSort(intarr[],intn)voidshellpass(intarr[],intd,intn)voidshellSort(intarr[],intb,intn)voidbubbleSort(intarr[],intn)voidQuickSort(int〃输出列表函数//插入排序注意监视哨作用//希尔排序一趟d为步长//希尔排序//冒泡排序〃快速排序重点的排序//选择排序//建堆i为根节点n为个数//堆排序//主函数各函数之间的关系如图3-3：mainO图3-3程序中各函数之间的关系4详细设计〃插入排序注意监视哨作用直接插入排序，arr[0]为监视哨的作用。把未排好序的第一个数依次与已排好序的比较，寻找到合适位置插入。详细设计如下：voidinsertSort(intarr[],intn){〃插入排序注意监视哨作用inti,j;for(i=2;i<=n;i++){〃安放监视哨arr[0]=arr[i];〃安放监视哨j=i-1;while(arr[0]<arr[j]){arr[j+1]=arr[j];//j--//j--很重要}arr[j+1]=arr[0];printf("Thatis%dtimesofwhistle%2d:",i-1,arr[0]);//自己学习观察用;printarr(arr,10);}}(2)希尔排序，希尔排序中不需要安放监视哨，while(j>0&&arr[0]<arr[j]);为设置终止条件。//希尔排序一趟d为步长;voidshellpass(intarr[],int//希尔排序一趟d为步长;inti,j;

for(i=d+1;i<=n;i++)〃注意类比插入排序；没有监视哨if(arr[i]<arr[i-d]){arr[0]=arr[i];j=i-d；do{arr[j+d]=arr[j];〃每一组内向后移动；j=j-d;}while(j>0&&arr[0]<arr[j]);〃由于没有监视哨所以必须设置终止条件;arr[j+d]=arr[0];}〃观察学习用〃希尔排序〃这里一定注意“1”是否执行问题边界//冒泡排序printarr(arr,10);〃观察学习用〃希尔排序〃这里一定注意“1”是否执行问题边界//冒泡排序doshellpass(arr,b,n);b=b/2;}while(b>=1);//printarr(arr,10);}冒泡排序：voidbubbleSort(intarr[],intn){inti,j;for(i=n;i>=1;i--){for(j=1;j<=i;j++){if(arr[j]>arr[j+1]){arr[0]=arr[j];arr[j]=arr[j+1];arr[j+1]=arr[0];}}}}快速排序，重要的是设置枢值，枢值的选择是任意的，每一次交换数据时要比较是否〃快速排序重点的排序！！！！！！！！！！j>p或i<p，执行结束的条件是i=j。voidQuickSort(intdata[],intleft,intright){

intp=left;//p为枢值inti=left,j=right;data[0]=data[left];//data[0]类似监视哨作用while(i<=j){while(data[j]>=data[0]&&j>=p)j--;if(j>=p){data[p]=data[j];p=j;}printarr(data,10);while(data[i]<=data[0]&&i<=p)i++;if(i<=p){data[p]=data[i];p=i;}printarr(data,10);}data[p]=data[0];printf("结束一次,Resultis:\n");printarr(data,10);printf(”下一次开始:\n");if(p-left>1)QuickSort(data,left,p-1);if(right-p>1)QuickSort(data,p+1,right);}选择排序，设定最小值记录min。〃快速排序重点的排序！！！！！！！！！！voidselectSort(intarr[],intn){inti,j,min;for(i=1;i<n;i++){min=i;for(j=i+1;j<=n;j++)if(arr[min]>arr[j])min=j;注意枢值的选择是任意的！！！！语句声明必须放在最前面注意〃递归开始枢值左边〃递归开始枢值左边//选择排序arr[0]=arr[i];

arr[i]=注意枢值的选择是任意的！！！！语句声明必须放在最前面注意〃递归开始枢值左边〃递归开始枢值左边//选择排序}}(5)堆排序，建堆是重点，巧妙的利用了根节点与孩子节点的关系child=2*i或者child=2*i+i在比较是否越界时与利用child<=n和child<n&&arr[child+1]>arr[child].这个思想很值得学习。voidshift(intarr[],inti,intn)//i为根节点n为一共有的个数建堆{intchild;child=2*i;//i的左孩子为2*i,右孩子为2*i+1arr[0]=arr[i];while(child<=n){if(child<n&&arr[child+1]>arr[child])//让child指向孩子中较大的一个{child=child+1;}if(arr[0]<arr[child])〃如果孩子节点大{arr[i]=arr[child];〃交换孩子节点和根节点i=child;child=2*i;}elsebreak;}arr[i]=arr[0];〃将根放在合适位置}//堆排序对a[1...n]进行排序//将a[1...n]//堆排序对a[1...n]进行排序//将a[1...n]建成大根堆//进行n-1趟排序〃交换堆顶元素和最后一个元素//将a[1...i-1]重建为堆inti;for(i=n/2;i>=1;i--){shift(arr,i,n);}for(i=n;i>=2;i--){arr[0]=arr[1];arr[1]=arr[i];arr[i]=arr[0];shift(arr,1,i-1);}5调试分析（1）采用在关键位置插入输出语句进行查看，自我感觉这种方法很好，直观。（2）在进行快速排序时，自我感觉没错，编译时报错，检查之后是把赋值语句放在声明语句之前，（data[0]=data[left];intp=leftinti=left,j=right;正确应是intp=leftinti=left,j=right;data[0]=data[left];）声明在前。（3）自己注意的是以后选择变量最好见名知意的，会减少很多错误，避免把自己绕进去，整糊涂了。（4）在进行堆排序时花费了很长时间，主要是在建堆的时候，没有体会全面，