C語言冒泡排序及其復雜度分析

• 問題：給定一個整數序列，按照從小到大的順序（確切地說，是非遞減的順序）排列序列中的整數。
• 輸入：一個整數序列。
• 輸出：整數序列，其中的整數升序排列。

因為譚浩強的C語言教材，大家最熟悉的可能就是冒泡排序。
下面是冒泡排序的一個C語言實現，a是數組首地址， size 是數組元素的個數。

冒泡排序的思想，是讓最大的數浮動到數組最後的位置，其次大的數浮動到數組倒數第二個位置……
當然，你也可以從大到小排序，也可以從後向前冒泡。其特征操作是相鄰元素的比較和交換。

void bubble_sort(int *a, int size)
{
  int i, j, t;
  for(i = 1; i < size; ++i){
    for(j = 0; j < size -i; ++j){
      if(a[j] > a[j+1]){
        t = a[j];
        a[j] = a[j+1];
        a[j+1] = t;
      }
    } // end for j
  }// end for i
}

時間復雜度分析。其外層循環執行 N - 1次。內層循環最多的時候執行N次，最少的時候執行1次，平均執行 (N+1)/2次。
所以循環體內的比較交換約執行 (N - 1)(N + 1) / 2 = (N^2 - 1)/2（其中N^2是仿照Latex中的記法，表示N的平方）。按照計算復雜度的原則，去掉常數，去掉最高項系數，其復雜度為O(N^2)。

冒泡算法的性能改進。上述算法的性能還有改進的空間。給定一個整數序列 [9, 3, 4, 5, 7]，每完成一次上述算法的外層循環，整數序列變化為：

9, 3, 4, 5, 7
3, 4, 5, 7, 9 (i = 1)
3, 4, 5, 7, 9 (i = 2)
3, 4, 5, 7, 9 (i = 3)
3, 4, 5, 7, 9 (i = 4)

我們發現當第一次外層循環完成後，排序就完成了。後面的循環只有比較，而沒有交換。
當一次外層循環中，相鄰的元素沒有發生交換，就說明數組已經是有序的了，這時可以跳出循環。
這樣，我們可以設置一個布爾變量，記錄一次外層循環中是否發生交換，如果未發生交換，算法就返回。

改進的冒泡排序的C語言實現如下：

void bubble_sort_enhanced(int *a, int size)
{
    int i, j, t;
    unsigned char swapped;
    for(i = 1; i < size; ++i) {
        swapped = 0;
        for(j = 0; j < size - i; ++j) {
            if(a[j] > a[j+1]){
                t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
                swapped = 1;
            }
        }
        if(!swapped)
            break;
    }
}

按照改進的算法，對於一個已經有序的數組，算法完成第一次外層循環後就會返回。
實際上只發生了 N - 1次比較，所以最好的情況下，該算法復雜度是O(N)。

2015-03-18 Wed