C語言對數組元素進行冒泡排序的實現

在實際開發中,有很多場景需要我們將數組元素按照從大到小(或者從小到大)的順序排列,這樣在查閱數據時會更加直觀,例如:

  • 一個保存瞭班級學號的數組,排序後更容易分區好學生和壞學生;
  • 一個保存瞭商品單價的數組,排序後更容易看出它們的性價比。

對數組元素進行排序的方法有很多種,比如冒泡排序、歸並排序、選擇排序、插入排序、快速排序等,其中最經典最需要掌握的是「冒泡排序」。

以從小到大排序為例,冒泡排序的整體思想是這樣的:

  • 從數組頭部開始,不斷比較相鄰的兩個元素的大小,讓較大的元素逐漸往後移動(交換兩個元素的值),直到數組的末尾。經過第一輪的比較,就可以找到最大的元素,並將它移動到最後一個位置。
  • 第一輪結束後,繼續第二輪。仍然從數組頭部開始比較,讓較大的元素逐漸往後移動,直到數組的倒數第二個元素為止。經過第二輪的比較,就可以找到次大的元素,並將它放到倒數第二個位置。
  • 以此類推,進行 n-1(n 為數組長度)輪“冒泡”後,就可以將所有的元素都排列好。

整個排序過程就好像氣泡不斷從水裡冒出來,最大的先出來,次大的第二出來,最小的最後出來,所以將這種排序方式稱為冒泡排序(Bubble Sort)。

下面我們以“3  2  4  1”為例對冒泡排序進行說明。

第一輪  排序過程
3  2  4  1    (最初)
2  3  4  1    (比較3和2,交換)
2  3  4  1    (比較3和4,不交換)
2  3  1  4    (比較4和1,交換)
第一輪結束,最大的數字 4 已經在最後面,因此第二輪排序隻需要對前面三個數進行比較。

第二輪  排序過程
2  3  1  4 (第一輪排序結果)
2  3  1  4 (比較2和3,不交換)
2  1  3  4 (比較3和1,交換)
第二輪結束,次大的數字 3 已經排在倒數第二個位置,所以第三輪隻需要比較前兩個元素。

第三輪  排序過程
2  1  3  4  (第二輪排序結果)
1  2  3  4  (比較2和1,交換)

至此,排序結束。

算法總結及實現

對擁有 n 個元素的數組 R[n] 進行 n-1 輪比較。

第一輪,逐個比較 (R[1], R[2]),  (R[2], R[3]),  (R[3], R[4]),  …….  (R[N-1], R[N]),最大的元素被移動到 R[n] 上。

第二輪,逐個比較 (R[1], R[2]),  (R[2], R[3]),  (R[3], R[4]),  …….  (R[N-2], R[N-1]),次大的元素被移動到 R[n-1] 上。
。。。。。。
以此類推,直到整個數組從小到大排序。

具體的代碼實現如下所示:

#include <stdio.h>
int main(){
  int nums[10] = {4, 5, 2, 10, 7, 1, 8, 3, 6, 9};
  int i, j, temp;
  //冒泡排序算法:進行 n-1 輪比較
  for(i=0; i<10-1; i++){
    //每一輪比較前 n-1-i 個,也就是說,已經排序好的最後 i 個不用比較
    for(j=0; j<10-1-i; j++){
      if(nums[j] > nums[j+1]){
        temp = nums[j];
        nums[j] = nums[j+1];
        nums[j+1] = temp;
      }
    }
  }
  
  //輸出排序後的數組
  for(i=0; i<10; i++){
    printf("%d ", nums[i]);
  }
  printf("\n");
  
  return 0;
}

運行結果:
1 2 3 4 5 6 7 8 9 10

優化算法

上面的算法是大部分教材中提供的算法,其中有一點是可以優化的:當比較到第 i 輪的時候,如果剩下的元素已經排序好瞭,那麼就不用再繼續比較瞭,跳出循環即可,這樣就減少瞭比較的次數,提高瞭執行效率。

未經優化的算法一定會進行 n-1 輪比較,經過優化的算法最多進行 n-1 輪比較,高下立判。

優化後的算法實現如下所示:

#include <stdio.h>
int main(){
  int nums[10] = {4, 5, 2, 10, 7, 1, 8, 3, 6, 9};
  int i, j, temp, isSorted;
  
  //優化算法:最多進行 n-1 輪比較
  for(i=0; i<10-1; i++){
    isSorted = 1; //假設剩下的元素已經排序好瞭
    for(j=0; j<10-1-i; j++){
      if(nums[j] > nums[j+1]){
        temp = nums[j];
        nums[j] = nums[j+1];
        nums[j+1] = temp;
        isSorted = 0; //一旦需要交換數組元素,就說明剩下的元素沒有排序好
      }
    }
    if(isSorted) break; //如果沒有發生交換,說明剩下的元素已經排序好瞭
  }
  for(i=0; i<10; i++){
    printf("%d ", nums[i]);
  }
  printf("\n");
  
  return 0;
}

我們額外設置瞭一個變量 isSorted,用它作為標志,值為“真”表示剩下的元素已經排序好瞭,值為“假”表示剩下的元素還未排序好。

每一輪比較之前,我們預先假設剩下的元素已經排序好瞭,並將 isSorted 設置為“真”,一旦在比較過程中需要交換元素,就說明假設是錯的,剩下的元素沒有排序好,於是將 isSorted 的值更改為“假”。

每一輪循環結束後,通過檢測 isSorted 的值就知道剩下的元素是否排序好。

到此這篇關於C語言對數組元素進行冒泡排序的實現的文章就介紹到這瞭,更多相關C語言數組冒泡排序內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: