C語言之常用幾種排序

微信公眾號：嵌入式開發(fā)圈
關注可了解更多的教程。問題或建議，請公眾號留言;
如果你覺得本文對你有幫助，歡迎贊賞

▲長按圖片保存可分享至朋友圈

冒泡排序

假設要對含有n個數(shù)的序列進行升序排列，冒泡排序算法步驟是：

1、從存放序列的數(shù)組中的第一個元素開始到最后一個元素，依次對相鄰兩數(shù)進行比較，若前者大后者小，則交換兩數(shù)的位置；

2、第1趟結束后，最大數(shù)就存放到數(shù)組的最后一個元素里了，然后從第一個元素開始到倒數(shù)第二個元素，依次對相鄰兩數(shù)進行比較，若前者大后者小，則交換兩數(shù)的位置；

3、重復步驟1 n-1趟，每趟比前一趟少比較一次，即可完成所求。

例1、隨機產(chǎn)生10個100以內的數(shù)，將其用冒泡法按升序排列后輸出。

編程思路：用最后一個數(shù)與前一個數(shù)比較，若比前一個數(shù)小

則交換位置，然后再與前一個數(shù)比較，若比前一個數(shù)小再交換

位置，知道比前一個數(shù)大或者已經(jīng)在最前面！如此循環(huán)8次就可以排好循序！

 1#include   2#include   3#define n?10   4int main(void)  5{  6 int a[n],i,j,t;  7 printf("隨機產(chǎn)生10個100以內的數(shù):\n");  8 for(i=0;i 9 { 10 a[i]?=?rand()%100; 11 printf("%d\n",a[i]); 12 } 13 printf("輸出:\n"); 14 for(j=1;j<=n-1;j++) 15 { /*n個數(shù)處理n-1趟*/ 16 for(i=0;i<=n-1-j;i++) 17 { /*每趟比前一趟少比較一次*/ 18 if(a[i]>a[i+1]) 19 { 20 t=a[i]; 21 a[i]=a[i+1]; 22 a[i+1]=t; 23 } 24 } 25 } 26 for(i=0;i27 { 28 printf("%d\n",a[i]); 29 } 30 return 0 ; 31}

運行結果:

選擇排序

選擇法排序是相對好理解的排序算法。假設要對含有n個數(shù)的序列進行升序排列，算法步驟是：

1、從數(shù)組存放的n個數(shù)中找出最小數(shù)的下標（算法見下面的“求最值”），然后將最小數(shù)與第1個數(shù)交換位置；

2、除第1個數(shù)以外，再從其余n-1個數(shù)中找出最小數(shù)（即n個數(shù)中的次小數(shù)）的下標，將此數(shù)與第2個數(shù)交換位置；

3、重復步驟1 ?n-1趟，即可完成所求。

代碼案例實現(xiàn):

 1#include   2#include   3#define n?10   4int main()  5{  6 int a[n],i,j,k,t;  7 printf("隨機產(chǎn)生10個100以內的數(shù):\n");  8 for(i=0;i 9 { 10 a[i]?=?rand()%100; 11 printf("%d\n",a[i]); 12 } 13 printf("輸出:\n"); 14 for(i=0;i-1;i++) /*處理n-1趟*/ 15 { 16 k?=?i; /*總是假設此趟處理的第一個（即全部數(shù)的第i個）數(shù)最小，k記錄其下標*/ 17 for(j=i+1;j18 { 19 if(a[j]?< a[k]) 20 k?=?j; 21 } 22 if (k?!=?i) 23 { 24 t?=?a[i]; 25 a[i]?=?a[k]; 26 a[k]?=?t; 27 } 28 } 29 for(i=0;i30 printf("%d\n",a[i]); 31 return 0 ; 32}

運行結果:

隨機產(chǎn)生10個100以內的數(shù)字,排序后輸出

插入排序

插入法排序的要領就是每讀入一個數(shù)立即插入到最終存放的數(shù)組中，每次插入都使得該數(shù)組有序。

代碼案例:

 1#include   2#include   3#define n?10   4  5int main()  6{  7 int a[n]={-1,3,6,9,13,22,27,32,49}; /*注意留一個空間給待插數(shù)*/  8 int x,j,k;  9 x?=?rand()%100; 10 printf("隨機產(chǎn)生x的值為:%d\n",x); 11 if(x>a[n-2]) 12 { 13 a[n-1]=x?; /*比最后一個數(shù)還大就往最后一個元素中存放*/ 14 } 15 else /*查找待插位置*/ 16 { 17 j=0; 18 while(?j<=n-2 &&?x>a[j]) 19 { 20 j++; 21 } 22 for(k=n-2;?k>=j;?k--) 23 { /*從最后一個數(shù)開始直到待插位置上的數(shù)依次后移一位*/ 24 a[k+1]=a[k]; 25 } 26 a[j]=x; /*插入待插數(shù)*/ 27 } 28 printf("輸出:\n"); 29 for(j=0;j<=n-1;j++) 30 printf("%d??",a[j]); 31 return 0 ; 32}

運行結果:

隨機產(chǎn)生一個數(shù)插入到已有的數(shù)組中，排序后輸出:

歸并排序

即將兩個都升序（或降序）排列的數(shù)據(jù)序列合并成一個仍按原序排列的序列。

代碼案例:

 1#include   2#include   3#define m?6  4#define n?4  5int main()  6{  7 int a[m]={-3,6,19,26,68,100}?,b[n]={8,10,12,22};  8 int i,j,k,c[m+n];  9 int l?; 10 i=j=k=0; 11 printf("a數(shù)組的元素:\n"); 12 for(l?= 0 ;?l?< m ; l++) 13 { 14 printf("%d??",a[l]); 15 } 16 printf("\nb數(shù)組的元素:\n"); 17 for(l?= 0 ;?l?< n ; l++) 18 { 19 printf("%d??",b[l]); 20 } 21 printf("\n合并后的數(shù)組元素:\n"); 22 while(i/*將a、b數(shù)組中的較小數(shù)依次存放到c數(shù)組中*/ 23 { 24 if(a[i]25 { 26 c[k]=a[i]; 27 i++; 28 } 29 else 30 { 31 c[k]=b[j]; 32 j++; 33 } 34 k++; 35 } 36 while(i>=m?&&?j/*若a中數(shù)據(jù)全部存放完畢，將b中余下的數(shù)全部存放到c中*/ 37 { 38 c[k]=b[j]; 39 k++; 40 j++; 41 } 42 while(j>=n?&&?i/*若b中數(shù)據(jù)全部存放完畢，將a中余下的數(shù)全部存放到c中*/ 43 { 44 c[k]=a[i]; 45 k++; 46 i++; 47 } 48 for(i=0;i49 printf("%d??",c[i]); 50 return 0 ; 51}

運行結果: