在實際開發(fā)中，有很多場景需要我們將數(shù)組元素按照從大到?。ɑ蛘邚男〉酱螅┑捻樞蚺帕校@樣在查閱數(shù)據(jù)時會更加直觀，例如：

• 一個保存了班級學(xué)號的數(shù)組，排序后更容易分區(qū)好學(xué)生和壞學(xué)生；
• 一個保存了商品單價的數(shù)組，排序后更容易看出它們的性價比。

對數(shù)組元素進(jìn)行排序的方法有很多種，比如冒泡排序、歸并排序、選擇排序、插入排序、快速排序等，其中最經(jīng)典最需要掌握的是「冒泡排序」。

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

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

整個排序過程就好像氣泡不斷從水里冒出來，最大的先出來，次大的第二出來，最小的最后出來，所以將這種排序方式稱為冒泡排序（Bubble Sort）。

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

第一輪  排序過程
3  2  4  1    （最初）
2  3  4  1    （比較3和2，交換）
2  3  4  1    （比較3和4，不交換）
2  3  1  4    （比較4和1，交換）
第一輪結(jié)束，最大的數(shù)字 4 已經(jīng)在最后面，因此第二輪排序只需要對前面三個數(shù)進(jìn)行比較。

第二輪  排序過程
2  3  1  4 （第一輪排序結(jié)果）
2  3  1  4 （比較2和3，不交換）
2  1  3  4 （比較3和1，交換）
第二輪結(jié)束，次大的數(shù)字 3 已經(jīng)排在倒數(shù)第二個位置，所以第三輪只需要比較前兩個元素。

第三輪  排序過程
2  1  3  4  （第二輪排序結(jié)果）
1  2  3  4  （比較2和1，交換）

至此，排序結(jié)束。

算法總結(jié)及實現(xiàn)

對擁有 n 個元素的數(shù)組 R[n] 進(jì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] 上。
。。。。。。
以此類推，直到整個數(shù)組從小到大排序。

具體的代碼實現(xiàn)如下所示：

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

運行結(jié)果：
1 2 3 4 5 6 7 8 9 10

優(yōu)化算法

上面的算法是大部分教材中提供的算法，其中有一點是可以優(yōu)化的：當(dāng)比較到第 i 輪的時候，如果剩下的元素已經(jīng)排序好了，那么就不用再繼續(xù)比較了，跳出循環(huán)即可，這樣就減少了比較的次數(shù)，提高了執(zhí)行效率。

未經(jīng)優(yōu)化的算法一定會進(jìn)行 n-1 輪比較，經(jīng)過優(yōu)化的算法最多進(jìn)行 n-1 輪比較，高下立判。

優(yōu)化后的算法實現(xiàn)如下所示：

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

我們額外設(shè)置了一個變量 isSorted，用它作為標(biāo)志，值為“真”表示剩下的元素已經(jīng)排序好了，值為“假”表示剩下的元素還未排序好。

每一輪比較之前，我們預(yù)先假設(shè)剩下的元素已經(jīng)排序好了，并將 isSorted 設(shè)置為“真”，一旦在比較過程中需要交換元素，就說明假設(shè)是錯的，剩下的元素沒有排序好，于是將 isSorted 的值更改為“假”。

每一輪循環(huán)結(jié)束后，通過檢測 isSorted 的值就知道剩下的元素是否排序好。

到此這篇關(guān)于C語言對數(shù)組元素進(jìn)行冒泡排序的實現(xiàn)的文章就介紹到這了,更多相關(guān)C語言數(shù)組冒泡排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論