多种排序算法
/* 用冒泡排序法对一维整型数组中的十个数升序排序*/
#include
int main()
{int i,j,t,a[10];
printf("Please input 10 integers:\n");
for(i=0;i<10;i++)
scanf("%d",&a[i]);
for(i=0;i<9;i++) /* 冒泡法排序*/
for(j=0;j<10-i-1;j++)
if(a[j]>a[j+1])
{ t=a[j];/* 交换a[i]和a[j] */
a[j]=a[j+1];
a[j+1]=t;
}
printf("The sequence after sort is:\n");
for(i=0;i<10;i++)
printf("%-5d",a[i]);
printf("\n");
}
其中i=0时：
j从0开始a[0],a[1]比较大小，把其中的较大者给a[1],然后j++,a[1]和a[2]再比较，再把两者中的
较大者给a[2],这样a[0],a[1],a[2]中的最大者已经交换到a[2]中，这样继续直到j=10-i-1=9这样
a[9]中的为10个数中的最大数。
然后i=1时:
由于最大数已找到并放到a[9]中，所以这一次循环j最大只需到10-i-1=8，即a[8]即可，再次从j=0开始a[j]和a[j+1]两两比较交换，最后次大数放到a[8]中
然后i++,继续...
当i=9时已经过9次两两比较完成所有排序，i<9不再成立退出比较。
对于n个数，只需要进行n-1次外循环的两两比较就完成排序。
至于按降序排列只需将if(a[j]>a[j+1])改为if(a[j] /* 用改进型冒泡排序法对一维整型数组中的十个数升序排序*/ #include int main() {int i,j,t,a[10],flag; printf("Please input 10 integers:\n"); for(i=0;i<10;i++) scanf("%d",&a[i]); for(i=0;i<9;i++) /* 改进型冒泡法排序*/ { flag=0; for(j=0;j<10-i-1;j++) if(a[j]>a[j+1]) { t=a[j]; /* 交换a[i]和a[j] */ a[j]=a[j+1]; a[j+1]=t; flag=1; } if(flag==0)break; } printf("The sequence after sort is:\n"); for(i=0;i<10;i++) printf("%-5d",a[i]); printf("\n"); } 这个和上面的实质一样，只是加了一个标志flag,当在一次大循环(即外层循环)内，在内层循环中如果没有发生一次交换，那么就表示a[0] #include main() { int n,i,j,*temp,*p,num; printf( "input sum of the numbers\n "); scanf( "%d ",&n); num=n; printf( "input numbers n <%d ",num); printf( "\n "); for (i=0;i getchar(); for (i=0;i for (j=0;j if (*(p+j+1) <*(p+j)) {*temp=*(p+j);*(p+j)=*(p+j+1);*(p+j+1)=*temp;} /*冒泡交换*/ printf( "the sort:\n "); for (i=0;i printf( "\n "); getchar(); #include main() { int a[]={12,6,4,9,3,8}; int *p=a; int i,j; for(i=0;i<5;i++) for(j=0;j<5;j++) {int middle; if(*(p+j)>*(p+j+1)) middle=*(p+j),*(p+j)=*(p+j+1),*(p+j+1)=middle; } for(i=0;i<6;i++) printf("%d",a[i]); } } 选择法： 最佳答案假设有5个数 5,4,3,2,1分别存放于数组a[0],a[1],a[2],a[3],a[4] 第一步以设基准索引i = 0, 则数a[0]为基准，也就是从a[1..4]中的数进行选择，若比基准小，则和基准做对换，反之则不动，设比较索引j=1开始比较。 j = 1 --> a[0]=5 > a[1]=4 则a[0] <==> a[1]，结果为4,5,3,2,1 j = 2 --> a[0]=4 > a[2]=3 则a[0] <==> a[2]，结果为3,5,4,2,1 j = 3 --> a[0]=3 > a[3]=2 则a[0] <==> a[3]，结果为2,5,4,3,1 j = 4 --> a[0]=2 > a[4]=1 则a[0] <==> a[4]，结果为1,5,4,3,2 由于j已经达到数组末尾则认为i=0即a[0]元素已经排序，而i=0并未达到数组尾部则i=i+1也就是i=2，然后重复上述步骤直到i=4为止。注意j的起始比较索引是随着i变化而变化的，它们的关系是j = i+1 例题1 #include void selectsort( int a[] , int n ) { int i , j , small , temp ; for( i = 0 ; i < n-1 ; i ++ ) { small = i ; for( j = i + 1 ; j < n ; j ++ ) if( a[j] < a[small] ) small = j ; if( small != i ) { temp = a[i] ; a[i] = a[small] ; a[small] = temp ; } } } int main() { int i ; int a[10] = { 5 , 3 , 7 , 2 , 8 , 12 , 9 , 1 , 4 , 19 }; selectsort( a , 10 ) ; for( i = 0 ; i < 10 ; i ++ ) printf("%d\t",a[i]); putchar('\n'); return 0 ; } 例题2 #include"stdio.h" void main() { int a[10]={2,3,1,6,7,8,9,10,4,5}; for(int i=0;i<10;i++) { int minindex=i; for(int j=i+1;j<10;j++)//这是找出第i个最小的。{ if(a[j] minindex=j; } int temp=a[i];//这是交换 a[i]=a[minindex]; a[minindex]=temp; } for(int k=0;k<10;k++) printf("%d ",a[k]); printf("\n"); } 例题3 #include "stdio.h" void main( ) { int a[10],*p,*q,*r,min; printf("请输入十个数："); for(p=a;p scanf("%d",p); for(p=a;p { for(q=p+1,r=p;q if(*r>*q) r=q; min=*p; *p=*r; *r=min; } 例题4 #include int fac(int a[],int n); main() { int b[10],i; for(i=0;i<10;i++) scanf("%d",&b[i]); fac(b,10); for(i=0;i<10;i++) printf("%5d",b[i]); } int fac(int *a,int n)/*你的原函数传递的是值,无法改变原数组的值*/ { int i,j,k,pos; for(i=0;i { k=*(a+i);/*假设最小的是开始比较的那一个*/ pos=i;/*位置也记录下来*/ for(j=i+1;j { if(k>*(a+j))/*如果发现比之前的数字小*/ { k=*(a+j);/*记录下来*/ pos=j;/*位置也记录下来*/ } } *(a+pos)=*(a+i);/*把最小那数的位置和当前的数字交换*/ *(a+i)=k;/*然后把最小的数记录在当前位置*/ } } 例题5 #include "stdio.h" void main( ) { int a[10],*p,*q,*r,min; printf("请输入十个数："); for(p=a;p scanf("%d",p); for(p=a;p { for(q=p+1,r=p;q if(*r>*q) r=q; min=*p; *p=*r; *r=min; } printf("排序后的数组："); for(p=a;p printf("%d ",*p); printf("\n"); } 冒泡 #include"stdio.h" main() { int i,j,t; int a[10]; for(i=0;i<10;i++) scanf("%d",&a[i]); for(i=0;i<9;i++) for(j=i+1;j<10;j++) if(a[i]>a[j]) {t=a[i];a[i]=a[j];a[j]=t;} for(i=0;i<=10;i++) printf("%d ",a[i]); } 二：选择 #include main() { int a[10],i,j,k,temp; for(i=0;i<10;i++) scanf("%d",&a[i]); for(i=0;i<9;i++) { k=i; for(j=i+1;j<10;j++) if(a[j] temp=a[k];a[k]=a[i];a[i]=temp; } for(i=0;i<10;i++) printf("%d ",a[i]); printf("\n"); } #define N 10 //数组元素个数 #include"stdio.h" void sort(int array[],int n) //排序函数 { int i,j,temp; for(i=0; i for(j=i+1; j { if(array[i]>array[j]) { //交换 temp=array[i]; array[i]=array[j]; array[j]=temp; } } } void main() //主函数 { //随便输入数组值 int array[N],i; printf("input 10 number:\n"); for(i=0; i { scanf("%d",&array[i]); } //调用排序函数 sort(array,N); //输出排序后的结果 for(i=0; i<10; i++) { printf("%d ",array[i]); } } 选择法排序是一种简单的容易实现的对数据排序的算法。 以整形数组元素为例，有数组A[10]（以C语言为例描述），即A[0]，A[1]，…，A[8]，A[9]（假设其元素均互不相同）。要求对其元素排序使之递增有序。 首先以一个元素为基准，从一个方向开始扫描，比如从左至右扫描，以A[0]为基准。 接下来从A[0]，…，A[9]中找出最小的元素，将其与A[0]交换。 然后将基准位置右移一位，重复上面的动作，比如，以A[1]为基准，找出A[1]~A[9]中最小的，将其与A[1]交换。 一直进行到基准位置移到数组最后一个元素时排序结束（此时基准左边所有元素均递增有序，而基准为最后一个元素，故完成排序）。 以下为一个用C描述的函数实现上述排序： void sort(int array[],int n) { // n 为数组元素个数 int i,j,k,temp; // i 为基准位置，j 为当前被扫描元素位置，k 用于暂存出现的较小的元素的位置 for(i=0;i {k=i;//初始化为基准位置 for(j=i+1;j { if (array[j] if(k!=i) { temp=array[i]; array[i]=array[k]; array[k]=temp; // 将此趟扫描得到的最小元素与基准互换位置 } } //for } } #include main() { int a[11],i,j,k,t; printf("input 10 numbers:\n"); for(i=1;i<11;i++) scanf("%d",&a[i]); printf("\n"); for(i=1;i<10;i++) {k=i; for(j=i+1;j<=10;j++) if(a[j] if(i!=k) {t=a[i];a[i]=a[k];a[k]=t;} } printf("The sorted numbers:\n"); for(i=1;i<11;i++) printf("%d ",a[i]); } 选择法 #include "stdio.h" void fun(int *p,int n) {int t; int i,j,k; for(i=0;i {k=i; for(j=1+i;j if(*(p+k)<*(p+j))k=j; if(k!=i) {t=*(p+i);*(p+i)=*(p+k);*(p+k)=t;} } } main() {int a[8],i; int *b=a; printf("Please input 8 numbers:\n"); for(i=0;i<8;i++) scanf("%d",b++); b=a; fun(b,8); for(i=0;i<8;i++) printf("%5d",a[i]); getchar(); } 冒泡法 #include main() { int a[]={12,6,4,9,3,8}; int *p=a; int i,j; for(i=0;i<5;i++) for(j=0;j<5;j++) {int middle; if(*(p+j)>*(p+j+1)) middle=*(p+j),*(p+j)=*(p+j+1),*(p+j+1)=middle; } for(i=0;i<6;i++) printf("%d",a[i]); } #include void main() { int a[10]; int i,j,t,*p; for(i=0;i<10;i++) scanf("%d",&a[i]); p=a; for(i=0;i<9;i++) { for(j=i+1;j<9-i;j++) if(*(p+i)<*(p+j)) { t=*(p+i); *(p+i)=*(p+j); *(p+j)=t; } } for(i=0;i<10;i++) printf("%d",a[i]); }