排序（一）

02-03

排序，是生活中非常常見的一個情景，以至於我都不想舉例子。

在本文中，只討論按照升序排序，因為降序排序是類似的。對於適用特殊方式的排序，這不在本文討論範圍內，不過可以用運算符重載封裝一下。

插入排序

插入排序很常見的例子：一是打牌的時候；二是一堆文件，我們按照順序依次把他們放到合適的位置。

插入排序時，我們有兩個數組。一個是存放亂序數據的數組 A，另一個是用來存放結果的數組 B，初始狀態為空。

插入排序時，我們依次從 A 中取出元素，插入到 B 中合適的位置。

插入排序浪費時間的原因在於，每次插入的元素如果不在末尾，演算法就必須移動那些元素，讓中間空出來一個位置。

template <class T> void insertionSort(T data[], int n){n for(int i = 1, j; i < n; ++i){n T tmp = data[i];n for(j = 1; j > 0 && tmp < data[j - 1]; j--) data[j] = data[j - 1];n data[j] = tmp;n }n}n

其漸進時間複雜度為 $Oleft( n^{2} right)$ .

選擇排序

選擇排序先找到位置不合適的元素，然後把它移動到合適的位置上。

template <class T> void selectionSort(T data[], int n){n for(int i = 0, j, least; i < n - 1; i++){n for(j = i + 1, least = i; j < n; j++)n if(data[j] < data[least]) least = j;n swap(data[least], data[i];n }n}n

其中的 swap 函數在 STL 的 algorithm 頭文件中有定義。

冒泡排序

將要排序的數組視為一個垂直的柱體。從數組底部向上掃描（從末尾向開頭），若相鄰的兩個元素逆序，則交換兩者。這只是第一次遍歷。後序遍歷中，不需要遍歷到數組開頭，只需要遍歷到第二個元素即可。這就是冒泡排序。

template <class T> void bubbleSort(T data[], int n){n for(int i = 0; i < n - 1; i++)n for(int j = n - 1; j > i; j--)n if(data[j] < data[j - 1]) swap(data[j], data[j - 1]);n}n

其漸進時間複雜度為 $Oleft( n^{2} right)$ 。

不過，如果在某一次遍歷時沒有發生交換，意味著已經排序完畢了，就可以跳出循環。

template <class T> void bubbleSort(T data[], int n){n for(int i = 0; i < n - 1; i++){n bool update = false;n for(int j = n - 1; j > i; j--)n if(data[j] < data[j - 1]){n swap(data[j], data[j - 1]);n update = true;n }n if(!update) break;n }n}n

下一篇文章中，將介紹漸進時間複雜度為 $Oleft( n log n right)$ 的幾個排序演算法。