偏序集排序（七）
從前一文章裡，我們發現「只是取出最長的一條鏈」就可以做到還不錯有效率的比較排序。 那麼不斷取出更多的長鏈，說不定就能夠掌握排序的精髓了！是的，我們把這個每一次找出最長可比鏈，得到的結果稱為 「貪婪鏈分解」（Greedy Chain Decomposition）。
貪婪鏈分解
對於一個偏序集 \((P, <)\)，如果我們每一次都找出最長鏈，並且將它從偏序集中移除，那麼就會得到一個分割（Partition）：\(C_1, C_2, \ldots, C_k\)。 其中每一個鏈 \(C_i\) 是一個集合，其內部任兩元素都可比較。嚴謹地描述的話，\(C_i\) 會被定義為子偏序集 \(P-\bigcup_{1\le j\le i-1} C_j\) 裡面的最長鏈。 值得一提的是，這個分割方法並不唯一。如果有許多最長鏈同時存在的情形時，我們只要隨意選擇一個最長鏈就行了。 這個分割方法可以保證鏈長遞減 \(|C_1\vert \ge \vert C_2\vert \ge \cdots \ge \vert C_k\vert \)。
貪婪鏈分解的性質
固定一組貪婪鏈分解 \((C_1, C_2, \ldots, C_k)\)。 對於 \(P\) 中的任何一個鏈 \(C\)，每一個 \(C\) 中的元素 \(v\) 都會對應到某個貪婪鏈分解當中的鏈 \(C_{id(v)}\)，其中 \(id(v)\) 是該鏈的編號。 於是呢，我們可以將鏈中的元素依照其 \(id(v)\) 值由小到大重新排列。 注意到，此時排列的順序並不是根據偏序集的大小關係來排序的、而是根據在貪婪鏈分解中對應到的鏈長來排序的。
假設依照 \(id(v)\) 的值排好序以後，\(C\) 中元素編號依序為 \(v_1, v_2, \ldots, v_{\vert C\vert }\)。 此時我們能有以下性質：
引理 28
對所有的 \(1\le j \le \vert C\vert \)，都有 \(|C_{id(v_j)}\vert \ge \vert C\vert - j + 1\)。
證明
由於鏈中元素已經按照 \(id(v)\) 的順序排序，去除掉前 \(j-1\) 個元素以後， \(C-\{v_1, v_2, \ldots, v_{j-1}\}\) （暫時記作 \(C'\)）裡頭剩餘的所有元素通通都會在 \(P-\bigcup_{1\le x\le id(j)-1} C_{x}\) （暫時記作 \(P'\)）裡面。 因此，根據定義，此時 \(C_{id(v_j)}\) 會是 \(P'\) 裡頭的最長鏈。而 \(C'\) 也是 \(P'\) 當中的某個鏈，於是有 \(|C_{id(v_j)}\vert \ge \vert C'\vert = \vert C\vert - j + 1\)，得證。
基於貪婪鏈分解的合併排序法
我們現在來探討有了這個貪婪鏈分解以後，可以怎麼把它應用在比較排序上頭。
每一條長鏈都是有全序排列的，有了很多條排好序的資料以後，我們通常會下意識地把它抓過來做合併排序法。 假設我們就按照一般的合併方法來排序：合併兩條鏈 \(C_x\) 與 \(C_y\) 需要使用 \(|C_x\vert +\vert C_y\vert \) 次比較。 那麼，由於每條鏈的長度都不固定，我們可以採用非常類似霍夫曼編碼演算法的方式，每一次貪心地挑選兩條最短的鏈進行合併。 不難證明，如此進行合併後，所需要的總比較次數 \(T_{合併貪婪鏈}\) 不超過
\[ T_{合併貪婪鏈} \le n + \sum_{i=1}^k \vert C_i\vert \log \frac{n}{\vert C_i\vert }\text{。} \]
這個演算法把它寫下來會變這樣：
- 第一步：進行貪婪鏈分解，得出 \(C_1, \ldots, C_k\)。
- 第二步：重複以下操作直到只剩下一條鏈（也就是排序完畢）
- 每一次挑選最短的兩個鏈，然後利用合併排序法的合併步驟將它們合併起來。
定理 29
基於貪婪鏈分解的合併排序法，其比較次數上界為 \(O(\log e(P)) + n\)。這個常數可以是 6.33 左右。
證明大綱
詳細的證明我們明天講。 但基本上，這個證明要做下面的事情：
- （一）我們得先證明加強版的引理 26： \[4\log e(P) + nH(P) \ge n\log n\]
- （二）根據貪婪鏈分解定義出直鏈和多胞形 \(\mathcal{C}(P)\) 上面的一個點 \(z\)。
根據這個點的值，找出 \(nH(P)\) 與 \(T_{合併貪婪鏈}\) 之間的關聯。 - （三）利用引理 27，先把最長鏈挑出來，然後說明剩下的比較次數可以被 \(O(\log e(P))\) 處理掉。
然後就得證啦！