冒泡排序

思想

重復地走訪要排序的數列，一次比較兩個元素，如果它們的順序不符合要求就交換它們的位置。N個數需要N - 1趟排序，每一趟排序使得最大數冒出（升序）或最小數冒出（降序）。

實現

/**
 * @brief    交換兩指針指向的對象的值
 */
void Swap(int *a, int *b);

傳統冒泡排序的C語言實現如下：

//升序方式
void BubbleSort(int a[], int n)
{
    int i, j;
 
    for(i = 0; i < n - 1; ++i)
        for(j = 0; j < n - 1 - i; ++j)
            if(a[j] > a[j + 1])
                Swap(a + j, a + j + 1);
}

改進

設比較標志法

• 思想
  普通的冒泡排序，即使原數列已經有序，仍然會進行N - 1趟排序。可以加入一標志性變量，用於標志某一趟排序過程中是否有數據交換。如果進行某一趟排序時並沒有進行數據交換，則說明數據已經按要求排列好，可立即結束排序，避免不必要的比較過程。如對序列3 1 4 5 6進行排序時，只進行2趟算法就結束了（第二趟沒有發生交換使得排序提前結束）。注意，當輸入序列是逆序的，該算法和傳統冒泡排序進行了一樣多次比較。

• 算法實現

  void FlagedBubbleSort(int a[], int n)
  {
  int i, j, swaped;
  
  for(i = 0; i < n - 1; ++i)
  {
      swaped = 0;
      for(j = 0; j < n - 1 - i; ++j)
          if(a[j] > a[j + 1])
          {
              swaped = 1;
              Swap(a + j, a + j + 1);
          }
      if(!swaped)
          break;
  }
  }

剔除法

• 思想
  假設某一位置pos後的元素都已排序，而pos前的元素未排序完，那麼上述算法仍然會掃描pos位置後的元素。因此，可設置一標志性變量pos，用於記錄每趟排序中最後一次進行交換的位置。由於pos位置後的元素均已排序完，故在進行下一趟排序時只要掃描到pos位置即可。可形象地認為pos位置後的n-pos+1個元素都被從待排序列中剔除了。

• 算法實現

  void RejectBubbleSort(int a[], int n)
  {
  int i, high, rpos;
  
  high = n - 1;              
  while(high > 0)
  {
      rpos = 0;
      for(i = 0; i < high; ++i)
          if(a[i] > a[i + 1])
          {
              rpos = i;             //記錄交換位置
              Swap(a + i, a + i + 1);
          }
      high = rpos;                     //下一趟應該掃描到達的位置
  }
  }

雙向剔除法

• 思想
  上面的剔除法只能處理某一方向上的已排序子序列，使用雙向的掃描可進一步優化冒泡排序。

• 算法實現

  void DoubleBubbleSort(int a[], int n)
  {
  int i, j;
  int low = 0, high = n - 1;
  int lpos, rpos;
  
  while(low < high)
  {
      rpos = low;
      for(i = low; i < high; ++i)         //正向冒泡
          if(a[i] > a[i + 1])
          {
              Swap(a + i, a + i + 1);
              rpos = i;
          }
      high = rpos;
  
      lpos = high;
      for(j = high; j > low; --j)         //反向冒泡
          if(a[j] < a[j - 1])
          {
              Swap(a + j, a + j - 1);
              lpos = j;
          }
      low = lpos;
  }
  }