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

“冒泡”這個(gè)名字的由來是因?yàn)樵酱蟮脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端，故名。

這里以從小到大排序?yàn)槔M(jìn)行講解。

基本思想及舉例說明

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

下面以對(duì) 3  2  4  1 進(jìn)行冒泡排序說明。

第一輪 排序過程
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)在最后面，因此第二輪排序只需要對(duì)前面三個(gè)數(shù)進(jìn)行再比較。

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

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

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

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

對(duì)于具有N個(gè)元素的數(shù)組R[n]，進(jìn)行最多N-1輪比較；

第一輪，逐個(gè)比較（R[1], R[2]）,  （R[2], R[3]）,  （R[3], R[4]）,  …….  （R[N-1], R[N]） ;  最大的元素會(huì)被移動(dòng)到R[N]上。

第二輪，逐個(gè)比較（R[1], R[2]）,  （R[2], R[3]）,  （R[3], R[4]）,  …….  （R[N-2], R[N-1]）；第二大元素會(huì)被移動(dòng)到R[N-1]上。

。。。。

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

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

#include<stdio.h>
#include<stdlib.h>
#define N 8
void bubble_sort(int a[],int n);
//一般實(shí)現(xiàn)
void bubble_sort(int a[],int n)//n為數(shù)組a的元素個(gè)數(shù)
{
  //一定進(jìn)行N-1輪比較
  for(int i=0; i<n-1; i++)
  {
    //每一輪比較前n-1-i個(gè)，即已排序好的最后i個(gè)不用比較
    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)化實(shí)現(xiàn)
void bubble_sort_better(int a[],int n)//n為數(shù)組a的元素個(gè)數(shù)
{
  //最多進(jìn)行N-1輪比較
  for(int i=0; i<n-1; i++)
  {
    bool isSorted = true;
    //每一輪比較前n-1-i個(gè)，即已排序好的最后i個(gè)不用比較
    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;
}

最新評(píng)論