c语言几种排序法！！！
很多朋友是以谭浩强老师编的《c语言教程》作为学习c语言的入门教程的。书中涉及排序问题一般都以“冒泡法”和“选择法”实现。为了扩大视野，增加学习编程的兴趣，我参阅了有关书籍，整理了几种排序法，写出来同大家共勉。
让我们先定义一个整型数组a[n],下面用五种方法对其从小到大排序。
（1）“冒泡法”
冒泡法大家都较熟悉。其原理为从a[0]开始，依次将其和后面的元素比较,若a[0]>a，则交换它们，一直比较到a[n]。同理对a[1],a[2],...a[n-1]处理，即完成排序。下面列出其代码：
void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小*/ { int i,j,temp; for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) /*注意循环的上下限*/ if(a>a[j]) { temp=a; a=a[j]; a[j]=temp; } } void choise(int *a,int n) { int i,j,k,temp; for(i=0;i<n-1;i++) { k=i; /*给记号赋值*/ for(j=i+1;j<n;j++) if(a[k]>a[j]) k=j; /*是k总是指向最小元素*/ if(i!=k) { /*当k!=i是才交换，否则a即为最小*/ temp=a; a=a[k]; a[k]=temp; } } } void quick(int *a,int i,int j) { int m,n,temp; int k; m=i; n=j; k=a[(i+j)/2]; /*选取的参照*/ do { while(a -<k&&m<j) m++; /* 从左到右找比k大的元素*/ while(a[ n]>k&&n>i) n--; /* 从右到左找比k小的元素*/ if(m<=n) { /*若找到且满足条件，则交换*/ temp=a -; a -=a[n]; a[n]=temp; m++; n--; } }while(m<=n); if(m<j) quick(a,m,j); /*运用递归*/ if(n>i) quick(a,i,n); } void insert(int *a,int n) { int i,j,temp; for(i=1;i<n;i++) { temp=a; /*temp为要插入的元素*/ j=i-1; while(j>=0&&temp<a[j]) { /*从a开始找比a小的数，同时把数组元素向后移*/ a[j+1]=a[j]; j--; } a[j+1]=temp; /*插入*/ } } [NextPage]void shell(int *a,int n) { int i,j,k,x; k=n/2; /*间距值*/ while(k>=1) { for(i=k;i<n;i++) { x=a; j=i-k; while(j>=0&&x<a[j]) { a[j+k]=a[j]; j-=k; } a[j+k]=x; } k/=2; /*缩小间距值*/ } } #include<stdio.h> /*别偷懒，下面的"..."代表函数体，自己加上去哦！*/ void bubble(int *a,int n) { ... } void choise(int *a,int n) { ... } void quick(int *a,int i,int j) { ... } void insert(int *a,int n) { ... } void shell(int *a,int n) { ... } /*为了打印方便，我们写一个print吧。*/ void print(int *a,int n) { int i; for(i=0;i<n;i++) printf("%5d",a); printf("\n"); } main() { /*为了公平，我们给每个函数定义一个相同数组*/ int a1[]={13,0,5,8,1,7,21,50,9,2}; int a2[]={13,0,5,8,1,7,21,50,9,2}; int a3[]={13,0,5,8,1,7,21,50,9,2}; int a4[]={13,0,5,8,1,7,21,50,9,2}; int a5[]={13,0,5,8,1,7,21,50,9,2}; printf("the original list:"); print(a1,10); printf("according to bubble:"); bubble(a1,10); print(a1,10); printf("according to choise:"); choise(a2,10); print(a2,10); printf("according to quick:"); quick(a3, 0,9); print(a3,10); printf("according to insert:"); insert(a4,10); print(a4,10); printf("according to shell:"); shell(a5,10); print(a5,10); }
void shell_sort(int *x, int n){ int h, j, k, t; for (h=n/2; h>0; h=h/2) /*控制增量*/ { for (j=h; j<n; j++) /*这个实际上就是上面的直接插入排序*/ { t = *(x+j); for (k=j-h; (k>=0 && t<*(x+k)); k-=h) { *(x+k+h) = *(x+k); } *(x+k+h) = t; } }}void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小*/ { int i,j,temp; for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) /*注意循环的上下限*/ if(a[i]>a[j]) { temp=a[i]; // 楼主此处有误 a[i]=a[j]; // 楼主此处有误 a[j]=temp; } }
[解决办法]
不错~
[解决办法]
接分 。。。。。。。。。。。。。
[解决办法]
楼主的猫扑排序有问题
应该是这样的：
void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小*/ { int i,j,temp; for(i=0;i<n-1;i++) { for(j=0;j<n-1;j++) /*注意循环的上下限*/ { if(a[j]>a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } }}
[解决办法]
学习一下
[解决办法]
UP~~
[解决办法]
辛苦了楼主，顶起
[解决办法]
我也该学这个了，先收藏下，lz辛苦了~
[解决办法]
楼主的冒泡好像是选择void bubble(int *a,int n)
{
int i,j,temp;
for(i=0;i<n;i++)
for(j=n-1;j>i;j--)
if(a[j]<a[j-1])
{
temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
for(i=0;i<n;i++)
printf("%d \n",a[i]);
}
[解决办法]
顶一下，lz功德~
另外补充一点点：
基于交换的排序的核心是一次相邻的交换操作只能消除一个逆序（inversion）。而可以证明一个N个元素的序列中的逆序数平均为 N(N-1)/4，所以基于相邻的交换的排序法的时间复杂度都是O(n^2)，要打破就要采用远距离交换，比如 shell 法。
堆排序的算法时间复杂度稳定，选择它就不怕worst-case；
Shell法如果选取比较好的增量序列（比如sedgewick序列），速度上可以超过堆排序，但它不是稳定的排序算法。
归并排序一般不用于内部排序（空间占用大）。
快排有待研究，要特别注意正确的写法(特别是指针转换）
------解决方案--------------------
新人，进来学习一下。
顶，加油，楼主。
[解决办法]
up！！
[解决办法]
还有归并排序，堆排序、、、
[解决办法]
好详细的东东啊。LZ辛苦了
[解决办法]
mark