冒泡排序是排序算法的一種，思路清晰，代碼簡潔，常被用在大學生計算機課程中。

“冒泡”這個名字的由來是因為越大的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端，故名。

這里以從小到大排序為例進行講解。

基本思想及舉例說明

冒泡排序的基本思想就是不斷比較相鄰的兩個數(shù)，讓較大的元素不斷地往后移。經(jīng)過一輪比較，就選出最大的數(shù)；經(jīng)過第2輪比較，就選出次大的數(shù)，以此類推。

下面以對 3  2  4  1 進行冒泡排序說明。

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

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

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

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

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

對于具有N個元素的數(shù)組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]上。

。。。。

以此類推，直到整個數(shù)組從小到大排序。

下面給出了冒泡排序的一般實現(xiàn)和優(yōu)化實現(xiàn)。一般實現(xiàn)是教科書里常見的實現(xiàn)方法，無論數(shù)組是否排序好了，都會進行N-1輪比較； 而優(yōu)化實現(xiàn)，在數(shù)組已經(jīng)排序好的情況下，會提前退出比較，減小了算法的時間復雜度。

#include<stdio.h>
#include<stdlib.h>
#define N 8
void bubble_sort(int a[],int n);
//一般實現(xiàn)
void bubble_sort(int a[],int n)//n為數(shù)組a的元素個數(shù)
{
  //一定進行N-1輪比較
  for(int i=0; i<n-1; i++)
  {
    //每一輪比較前n-1-i個，即已排序好的最后i個不用比較
    for(int j=0; j<n-1-i; j++)
    {
      if(a[j] > a[j+1])
      {
        int temp = a[j];
        a[j] = a[j+1];
        a[j+1]=temp;
      }
    }
  }
}
//優(yōu)化實現(xiàn)
void bubble_sort_better(int a[],int n)//n為數(shù)組a的元素個數(shù)
{
  //最多進行N-1輪比較
  for(int i=0; i<n-1; i++)
  {
    bool isSorted = true;
    //每一輪比較前n-1-i個，即已排序好的最后i個不用比較
    for(int j=0; j<n-1-i; j++)
    {
      if(a[j] > a[j+1])
      {
        isSorted = false;
        int temp = a[j];
        a[j] = a[j+1];
        a[j+1]=temp;
      }
    }
    if(isSorted) break; //如果沒有發(fā)生交換，說明數(shù)組已經(jīng)排序好了
  }
}
int main()
{
  int num[N] = {89, 38, 11, 78, 96, 44, 19, 25};
  bubble_sort(num, N); //或者使用bubble_sort_better(num, N);
  for(int i=0; i<N; i++)
    printf("%d ", num[i]);
  printf("\n");
  system("pause");
  return 0;
}

最新評論