雞尾酒排序法

昨天我們介紹了泡沫排序法，但是，泡沫排序法最差情形 \(O(n^2)\) 的時間複雜度真的是緊的嗎？ 讓我們看看以下例子。

引理 2

對於這組輸入 \((a_1, a_2, \ldots, a_n) = (n, n-1, \ldots, 1)\)，泡沫排序法執行時間為 \(\Omega(n^2)\)。

證明

我們可以由數學歸納法證得，第 \(k\) 次迴圈過後，陣列會變成 \([n-k, \ldots, 1, n-k+1, n-k+2, \ldots, n]\)。 因此，在 \(1\) 回到最前面之前，都不算排好順序。也就是說，泡沫排序法最差執行時間是 \(\Theta(n^2)\) 跑不掉的。

雞尾酒排序法 Cocktail Sort

如果說由前往後，沒有辦法快速地把資料排好順序，那麼如果換個方式跑 for-loop，有沒有辦法變快呢？ 雞尾酒排序法，就是基於泡沫排序法進行修改而成的排序方法。它從左邊刷過去再從右邊刷回來：第一次把最大值放到最右邊去、然後把最小值推到最左邊、再把次大值放到右邊、再把次小值放到左邊…依此類推。 這個演算法的正確性證明與泡沫排序法相當雷同，因此時間複雜度也可以推得為 \(O(n^2)\)。 遺憾的是，引理 2 的例子也是這個演算法的最壞輸入之一：即在最壞情形下仍需 \(\Theta(n^2)\) 的執行時間。

插入排序法 Insertion Sort

如果每一次都由右往左把資料刷回來，第 \(k\) 次把 \(arr[k-1]\) 從右邊往左邊一直推， 那麼概念上會變成：每一次加入一筆新的資料後，不斷地往前擠，插入到正確的位置上。這個方法也可以視為泡沫排序法的一個變形。 而事實上這個方法無論在現行的 CPU 架構下或是理論上，都不比泡沫排序法來得差。因此許多教科書都會選擇直接介紹插入排序法而非氣泡排序法。

引理 3 1

如果輸入的資料中，每一筆資料距離其正確的位置皆不超過 \(k\) (\(k\ge 1\))，那麼泡沫排序法、雞尾酒排序法、以及插入排序法所需要的時間複雜度皆為 \(O(kn)\)。

我們注意到，無論是氣泡排序法、雞尾酒排序法、或是插入排序法，這些方法在更動資料的時候，都只會交換相鄰兩筆資料。 而整體的時間複雜度，也至少是「交換兩筆資料」這個動作執行的次數。 對於一個陣列 \(A\)，我們可以定義只能交換相鄰兩筆資料的情形下，欲將 \(A\) 排好順序最少需要的交換次數。 這個數值，我們把它稱之為「逆序數對(Inversions)」。