数据结构各种排序程序

《数据结构各种排序程序》由会员分享，可在线阅读，更多相关《数据结构各种排序程序（14页珍藏版）》请在金锄头文库上搜索。

1、数据结构各种排序程序数据结构各种排序程序数据结构中的排序算法,各有用处,比如: 1,直接插入排序,在序列基本有序的情况下,移动的次数比较少,但是比较次数是一样的 复杂度 O(n*n); 2,冒泡排序,这个不用说了吧,刚学 C 的人都懂了 3,希尔排序,只要是找出较好的增量,将数据排列成基本有序时,最后一次来一次直接插入排序,是对直接插入排序的改进.复杂度为O(n(3/2); 4,快速排序,算是所有排序中复杂度一般情况下比较好的算法,它设了一个枢轴,将它分为两部分,左边比它小,右边的比它大,复杂度为O(nlog n); 5,选择排序,和冒泡差不多的复杂度, 6,归并排序,这是一种稳定的排序方法,

2、将数据分为各个有序的部分,再组合为一个整体,只要用递归的方法. 7,还有基数排序,树形排序,堆排序,等等,这里不多说了,你多多学习多多消化吧,慢慢学吧,多看看课本的算法,自己实现一次,学完了你的编程能力就能很好的提高了.#include#includestruct nodeint key;r20;struct rnodeint key;int point;main()void print(struct node a20,int n);int creat();void shell(struct node a20,int n);int hoare(struct node a20,int l,int

3、 h);void quick1(struct node a20,int n);void quick2(struct node a20,int l,int h);void heap(struct node a20,int i,int m);void heapsort(struct node a20,int n);void merges(struct node a20,struct node a220,int h1,int mid,int h2);void mergepass(struct node a20,struct node a220,int l,int n);void mergesort(

4、struct node a20,int n);int yx(int m,int i);int radixsort(struct rnode a20,int n);int num,l,h,c;struct rnode s20;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(“ 7 基数排序 n

5、“);printf(“ 输入选择 (1-7,0 表示结束): “);scanf(“%d“,switch(c)case 1:num=creat();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(“output quick2sort result:n“);print(r,num);break;case 5:heapsort(r,num);break;case 6:merg

6、esort(r,num);print(r,num);break;case 7:radixsort(s,num);/main endvoid print(struct node a20,int n)int i;for(i=0;i=1;i-)ai.key=ai-1.key;k=n/2;while(k=1)for(i=k+1;ia0.key)j=j-k;aj+k=a0;k=k/2;for(i=0;i=x.key)j-;if(iaj+1.key)j+;if(aj.key0;i-)ai.key=ai-1.key;for(i=n/2;i=1;i-)heap(a,i,n);printf(“输出堆排序结果:n

7、“);for(v=n;v=2;v-)printf(“%5d“,a1.key);x.key=a1.key;a1.key=av.key;av.key=x.key;heap(a,1,v-1);printf(“%5d“,a1.key);for(i=0;i=2*l)h1=i;mid=h1+l-1;h2=i+2*l-1;merges(a,a2,h1,mid,h2);i=i+2*l;if(n-i)=l)for(j=i;j=n;j+)a2j.key=aj.key;elseh1=i;mid=h1+l-1;h2=n-1;merges(a,a2,h1,mid,h2);/mergepass endvoid merge

8、sort(struct node a20,int n)int l;struct node a220;l=1;while(ln)mergepass(a,a2,l,n);l=2*l;mergepass(a2,a,l,n);l=2*l;printf(“输出归并排序的结果:n“);/mergesort end/归并函数结束/基数排序/int yx(int m,int i)/分离关键字倒数第 i 位有效数字的算法int x;switch(i)case 1:x=m%10;break;case 2:x=(m%100)/10;break;case 3:x=(m%1000)/100;break;case 4:x

9、=(m%10000)/1000;break;return(x);/yx endint radixsort(struct rnode a20,int n)int f11,e11,i,j,k,l,p,d,t;for(i=1;i=n;i+)ai.key=ri-1.key;ai.point=i+1;an.point=0;p=1;printf(“输出关键字有效位数 dn“);scanf(“%d“,printf(“输出基数排序的结果:n“);for(i=1;i=d;i+)for(j=0;j=10;j+)fj=0;ej=0;while(p!=0)k=yx(ap.key,i);if(fk=0)fk=p;ek=p;elsel=ek;al.point=p;ek=p;p=ap.point;j=0;while(fj=0)j+;p=fj;t=ej;while(j10)j+;while(j10)if(fj!=0)at.point=fj;t=ej;at.point=0;t=p;while(t!=0)printf(“%5d“,at.key);t=at.point;printf(“n“);return(p);