各种排序方法的C语言实现

1、各种排序方法的C语言实现，并附注释。已经通过测试可直接复制粘贴运行！废话不说，直接上代码：#include "stdio.h"typedef struct int key;recordtype; /*定义数据结构*/void bubblesort(recordtype r,int n) /*冒泡排序*/ int i,j; /*int count=0; */ /*负责统计移动次数*/ for(i=1;i<n;i+) for(j=1;j<=n-i;j+) if(rj.key>rj+1.key) r0=rj; rj=rj+1; rj+1=r0; /*count+

2、; */ /*下边循环负责输出排序后的结果*/ for(i=1;i<=n;i+) printf("%d ",ri); printf("n"); /*printf("执行次数大致为 %dn",count); */ shellsort(recordtype r,int n) /*希尔排序*/int d,i,j; /*int count=0; */ /*负责统计移动次数*/ d=n/2; while(d>0) for(i=d+1;i<=n;i+) r0=ri; j=i-d; /*确定每组中ri的前一个位置*/ while(

3、j>0&&r0.key<rj.key) rj+d=rj; /*后移记录*/ j=j-d; /*count+;*/ /*得到前一个记录的位置*/ rj+d=r0; /*插入记录点到确定的位置*/ d=d/2; /*缩小步长值*/ /*下边循环负责输出排序后的结果*/ for(i=1;i<=n;i+) printf("%d ",ri); printf("n"); /* printf("执行次数大致为 %dn",count); */ insertsort(recordtype r,int n) /*直接插入

4、排序*/ int i,j; /*int count=0; */ /*负责统计移动次数*/ for(i=2;i<=n;i+) r0=ri; j=i-1;/* 有序区的最后一个记录*/ while(r0.key<rj.key) rj+1=rj-; /*count+;*/ rj+1=r0; /*下边循环负责输出排序后的结果*/ for(i=1;i<=n;i+) printf("%d ",ri); printf("n"); /* printf("执行次数大致为 %dn",count);*/ int partsort(reco

5、rdtype R,int low,int high) int i,j; recordtype temp; i=low; j=high;temp=Ri; do while(Rj.key>=temp.key)&&(i<j) j-; if(i<j) Ri+=Rj;/*从右向左扫描，查找第一个key小于temp.key的记录,并交换*/ while(Ri.key<=temp.key)&&(i<j) i+; if(i<j) Rj-=Ri; while(i!=j); /*i+后的i与j-后的j比较*/Ri=temp;return i; /

6、*一次划分算法*/void quicksort(recordtype R,int start,int end) /*快速*/int i;if(start<end) /*只有1个或没有时不用排序*/ i=partsort(R,start,end); /*一次划分*/ quicksort(R,start,i-1); /*递归处理左区间*/ quicksort(R,i+1,end); /*右*/ void selectsort(int r, int n) /*直接选择排序 */ int i,j,k,temp; /*int count=0;*/ /*负责统计移动次数*/ for (i=1; i&

7、lt;n; i+) /*对n个记录进行n-1趟简单选择排序*/ k=i; for (j=i+1; j<=n; j+) /*在无序区中选取最小记录*/ if (rj<rk) k=j; if (k!=i) temp=ri; ri=rk; rk=temp; /*count+; */ /*下边循环负责输出排序后的结果*/ for(i=1;i<=n;i+) printf("%d ",ri); printf("n"); /*printf("执行次数大致为 %dn",count); */void sift(recordtype r

8、,int i,int m) /*建立大根堆*/int j;recordtype t;t=ri;j=2*i;while (j<=m) if(j<m&&rj.key<rj+1.key) j+; if (t.key<rj.key) ri=rj; i=j; j=2*i; else break; ri=t;void heap(recordtype r , int n) /*堆排序算法*/*r 为排序数组，n为数组大小*/ int i; recordtype t; for (i=n/2;i>=1;i-) sift(r,i,n); for (i=n;i>1

9、;i-) t=r1; r1=ri; ri=t; sift(r,1 ,i-1); /*下边循环负责输出排序后的结果*/ for(i=1;i<=n;i+) printf("%d ",ri); printf("n"); /* printf("执行次数大致为 %dn",count);*/void merge(recordtype r,int low,int m,int high)recordtype r112; int i,j,k; i=low;j=m+1;k=0; while(i<=m&&j<=high)

10、if(ri.key<=rj.key) r1k=ri;k+;i+; else r1k=rj;k+;j+; while(i<=m) r1k=ri;k+;i+; while(j<=high) r1k=rj;k+;j+; for(i=low,k=0;i<=high;i+,k+) ri=r1k;void mergepass(recordtype r,int length,int n) /*一趟归并排序*/ int i,j; i=1; while(i+2*length-1<=n) merge(r,i,i+length-1,i+2*length-1); /*两个子序列长度相等的

11、情况*/ i=i+2*length; if(i+length-1<n) /*剩下两个子序列中，有一个长度小于length*/ merge(r,i,i+length-1,n);void mergesort(recordtype r,int n) /*归并排序*/ int length=1; int i; while(length<n) mergepass(r,length,n); length=2*length; /*下边循环负责输出排序后的结果*/ for(i=1;i<=n;i+) printf("%d ",ri); printf("n"

12、;); /* printf("执行次数大致为 %dn",count);*/*/*哥的华丽分割线，下边是主函，上边是各种排序方法*/*/ main() /*下面是用一个二维数组的三行来存储三种不同的测试数据*/recordtype a312= 0,6,13,19,23,37,39,41,45,48,58,86, 0,86,58,48,45,41,39,37,23,19,13,6, 0,23,13,48,86,19,6,41,58,37,45,39 ;recordtype r12;int i,j,m,n;system( "graftabl 936 "); c

13、lrscr(); /*这两行用于显示中文*/printf("请选择测试数据类型：正序 逆序 随机 【若跳出,请按】n");printf("您选择的是：");scanf("%d",&m);printf("n");while(m>0&&m<4) if(m=1) for(i=1;i<=11;i+) ri=am-1i; if(m=2) for(i=1;i<=11;i+) ri=am-1i; if(m=3) for(i=1;i<=11;i+) ri=am-1i;print

14、f("n");printf("您选择的是%d，为您提供的测试用数据是：",m); for(i=1;i<=11;i+) printf("%d ",ri); printf("n"); printf("n");printf("请选择排序算法：n(1)直接插入排序n(2)希尔排序n(3)冒泡排序n(4)快速排序n(5)直接选择排序n(6)堆排序n(7)堆排序n"); printf("n");printf("您选择的是：");scanf(&

15、quot;%d",&n);switch (n) case 1: printf("n直接插入排序前：n"); for(j=1;j<12;j+) printf("%d ",rj); printf("n直接插入排序结果为：n"); insertsort(r,11); printf("n"); break; case 2: printf("n希尔排序前：n"); for(j=1;j<12;j+) printf("%d ",rj); printf(&quo

16、t;n希尔排序结果为：n"); shellsort(r, 11); printf("n"); break; case 3: printf("n冒泡排序前：n"); for(j=1;j<12;j+) printf("%d ",rj); printf("n冒泡排序结果为：n"); bubblesort(r, 11); printf("n"); break; case 4: printf("n快速排序前：n"); for(j=1;j<12;j+) printf

17、("%d ",rj); printf("n快速排序结果为：n"); quicksort(r, 0,11); for(i=1;i<=11;i+) /*-这个输出比较特殊-*/ printf("%d ",ri); printf("n"); break; case 5: printf("n直接选择排序前：n"); for(j=1;j<12;j+) printf("%d ",rj); printf("n直接选择排序结果为：n"); selectsort

18、(r, 11); printf("n"); break; case 6: printf("n堆排序前：n"); for(j=1;j<12;j+) printf("%d ",rj); printf("n堆排序结果为：n"); heap(r, 11); printf("n"); break; case 7: printf("n归并排序前：n"); for(j=1;j<12;j+) printf("%d ",rj); printf("n归并排序结果为：n"); merg