排序实验1

【姓名】林文辉 【班号】计算机 164 【学号】2016011147 【Email】229088559@qq.com 排序 一、实验目的与任务 熟悉几种典型的排序方法，并对各种算法的特点，使用范围和效率有进一步的了解。

二、实验步骤（实验源码）运行截图（部分测试）：

程序源码：

#include #include typedef struct{ int key;int point;}node;node r[20];void print(node a[],int n);int creat();void shell(node a[],int n);int hoare(node a[],int l,int h);void quick1(node a[],int n);void quick2(node a[],int l,int h);void heap(node a[],int i,int m);void heapsort(node a[],int n);void merge(node a[],node a2[],int h1,int mid,int h2);void mergepass(node a[],node a2[],int l,int n);void mergesort(node a[],int n);int main(void){ int yx(int m,int i);int radixsort(node a[],int n);int num,l,h,c;c=1;while(c!=0){ printf(" 主菜单n");printf("1.输入关键字，以-9999 表示结束n");printf("2.希尔排序n");printf("3.非递归的快速排序n");printf("4.递归的快速排序n");printf("5.堆排序n");printf("6.归并排序n");printf("输入选择(1-6,0 表示结束):");scanf("%d",&c);switch(c){ case 1:num=creat();printf("记录中原始数据如下:n");print(r,num);break;case 2:shell(r,num);print(r,num);break;case 3:quick1(r,num);print(r,num);break;case 4:l=0;h=num-1;quick2(r,l,h);printf("输入非递归快速排序的结果:n");print(r,num);break;case 5:heapsort(r,num);break;

case 6:mergesort(r,num);print(r,num);break;} } } void print(node a[],int n){ int i;for(i=0;i=1;i--)a[i].key=a[i-1].key;k=n/2;while(k>=1){ for(i=k+1;i<=n;i++){ a[0].key=a[i].key;j=i-k;while((a[j].key>a[0].key)&&(j>=0)){ a[j+k].key=a[j].key;j=j-k;} a[j+k]=a[0];} k=k/2;} for(i=0;i

printf("输出希尔排序的结果:n");} int hoare(node a[],int l,int h){ int i,j;node x;i=1;j=h;x.key=a[i].key;do{ while((i=x.key))j--;if(i

void heap(node a[],int i,int m){ node x;int j;x.key=a[i].key;j=2*i;while(j<=m){ if(ja[j+1].key)j++;if(a[j].key0;i--)a[i].key=a[i-1].key;for(i=n/2;i>=1;i--)heap(a,i,n);printf("输出归并排序的结果:n");for(v=n;v>=2;v--){ printf("%5d",a[1].key);x.key=a[1].key;a[1].key=a[v].key;a[v].key=x.key;heap(a,1,v-1);} printf("%5d",a[1].key);for(i=0;i

k++;a2[k].key=a[i].key;i++;} while(j<=h2){ k++;a2[k].key=a[j].key;j++;} } void mergepass(node a[],node a2[],int l,int n){ int j,i,h1,mid,h2;i=0;while((n-i)>=2*l){ h1=i;mid=h1+l-1;h2=i+2*l-1;merge(a,a2,h1,mid,h2);i=i+2*l;} if((n-1)<=1)for(j=i;j<=n;j++)a2[j].key=a[j].key;else{ h1=i;mid=h1+l-1;h2=n-1;merge(a,a2,h1,mid,h2);} } void mergesort(node a[],int n){ int l;node a2[20];l=1;while(l三、实验总结 实验涉及四种常见的排序算法 希尔排序：实际上就是一种插入排序的体现，希尔排序算法通过设置一个间隔（一般

取的比较大），这样就可以把数据分为若干组，对每组进行插入排序，此数集合中的元素移位的长度是以间隔的长度为准，这样就实现了大步位移，紧接着缩小间隔，再重复操作直至间隔为 1（相当于直接插入排序）。

快速排序：很好的体现了分而治之的思想，以某个数为中间值，将这个数组划分成两部分，大于它的和小于它的分居左右，划分之后对这两部分进行同样的操作，一直分下去，直到每部分只有一个元素位置为止。本实验中涉及了两种快速排序的实现方法，一种是递归，一种是非递归，核心算法都是一样的，实现的方式有所不同，与以往的经验不同，在这里似乎递归方式实现的快速排序比非递归方式实现的快速排序更有效率一些。

堆排序：堆排序实际上是一种利用“堆”的选择排序，是一种不稳定排序，将待排序序列构造成一个大顶堆的形式，使得整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余 n-1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值。重复上述过程，便能实现排序的效果。

归并排序：把待排序数组从中间分开，一分为二，重复上述操作，拆分为单个元素数组，按照顺序两两组合为有序数组,再将生成的有序数组合并为大的有序数组，重复操作，直到合并成一个有序数组。

排序教学设计

数学活动;排序

数学排序教案

高考化学二轮主观题必刷题专题21,实验排序题（含答案解析）

幼儿园小班数学教案：排序