摘要訊息 : 利用元素的名次對元素進行排序.

0. 前言

名次在生活中非常常見, 看到名次, 大家可能第一時間就想起了大家在學校的時候, 成績的名次; 大家也可能想起對於某一類東西的評測名次... 要想有名次, 就必須有一個內容是可比較的, 也就必須有權的概念. 比如一個班裡的所有學生的名次, 以最終的成績為權, 然後進行名次排序.

本篇文章中, 我們主要討論的是升序的名次排序法, 也就是從小到大對元素進行排序. 對於降序的情況, 類似可得.

更新紀錄 :

• 2022 年 4 月 21 日進行第一次更新和修正.

1. 排序的穩定性

任意給定一個元素集合 $\mathscr {S}$, 經過排序之後, 一個元素 $e$ 在集合 $\mathscr {S}$ 中的位置是第 $k$ 位, $k$ 的值是集合 $\mathscr {S}$ 中比 $e$ 小的元素的數量. 現在如果不限定集合 $\mathscr {S}$ 的唯一性, 也就是集合 $\mathscr {S}$ 中可以出現重複的元素, 那麼排序演算法如何處理這些重複元素的順序關係到了一個排序演算法的穩定性 (stability).

定義 1. 設集合 $\mathscr {S}$ 中存在重複元素, 任取兩個元素 $e_{1} \in \mathscr {S}$ 和 $e_{2} \in \mathscr {S}$ 滿足 $e_{1} = e_{2}$ 且 $e_{1}$ 在集合中的位置排在 $e_{2}$ 之前. 現在用某一演算法 $\mathbb {A}$ 對集合 $\mathscr {S}$ 中的元素進行排序. 若排序之後, $e_{1}$ 仍然在 $e_{2}$ 之前, 那麼我們說排序演算法 $\mathbb {A}$ 是穩定的 (stable); 否則, 稱排序演算法 $\mathbb {A}$ 是不穩定的 (unstable).

例如設有集合 $\mathscr {S} = \left \{ B, C_{1}, P, A, C_{2}, K \right \}$ ($C_{1}$ 和 $C_{2}$ 在數值上相等, 下標僅用於區分在集合中的前後順序) 和排序演算法 $\mathbb {A}$. 使用 $\mathbb {A}$ 對 $\mathscr {S}$ 排序之後, 若有 $\displaystyle {\mathscr {S} = \left \{ A, B, C_{1}, C_{2}, K, P \right \},}$ 那麼 $\mathbb {A}$ 就是穩定的排序演算法; 若有 $\displaystyle {\mathscr {S} = \left \{ A, B, C_{2}, C_{1}, K, P \right \},}$ 那麼 $\mathbb {A}$ 就是不穩定的排序演算法.

2. 名次排序法

定義 2. 我們定義一個元素 $e$ 在集合 $\mathscr {S}$ 中的名次 $R_{e}$ 為 $\displaystyle {R_{e} = \mathscr {S} \text { 中所有小於 } e \text { 的元素數量} + \mathscr {S} \text { 中所有等於 } e \text { 且出現在其左側的元素數量}.}$

名次排序法是按照集合中元素的名次對集合進行排序. 由定義 2 我們可以看出, 名次排序法是穩定的排序演算法.

為了進行名次排序法, 我們必須首先計算每一個元素的名次. 首先, 我們要配置額外 $n$ 個空間用於儲存對應元素的名次. 然後任取 $e_{i} \in \mathscr {S}$, 比較剩餘元素和 $e_{i}$ 的大小. 若 $e_{i} > e_{j}$, 那麼就讓儲存名次空間中的第 $j$ 個元素增加一, 代表它的權重較大; 否則, 就讓儲存名次空間中的第 $i$ 個元素增加一. 接下來排除 $e_{i}$, 然後再取一個元素, 將其與剩餘的元素作比較. 不斷重複上述步驟, 直到 $\mathscr {S}$ 中只剩下一個元素為止. 其中, $i, j = 1, 2, ..., n, i \neq j$.

例題 1. 計算集合 $\mathscr {S} = \left \{ B, C_{1}, P, C_{2} \right \}$ 中各個元素的名次.

$解$ :

我們令 $\mathscr {R} = \left \{ 1, 1, 1, 1 \right \}$. 其中, $\mathscr {R}$ 中第 $i$ 個元素表示 $\mathscr {S}$ 中對應第 $i$ 個元素的名次.

我們選取元素 $B$ :

• 由於 $B < C_{1}$, 所以更新 $\mathscr {R}$ 為 $\mathscr {R} = \left \{ 1, 2, 1, 1 \right \}$;
• 由於 $B < P$, 所以更新 $\mathscr {R}$ 為 $\mathscr {R} = \left \{ 1, 2, 2, 1 \right \}$;
• 由於 $B < C_{2}$, 所以更新 $\mathscr {R}$ 為 $\mathscr {R} = \left \{ 1, 2, 2, 2 \right \}$.

我們選取元素 $C_{1}$ :

• 由於 $C_{1} < P$, 所以更新 $\mathscr {R}$ 為 $\mathscr {R} = \left \{ 1, 2, 3, 2 \right \}$;
• 由於 $C_{1} < C_{2}$ 不成立, 所以更新 $\mathscr {R}$ 為 $\mathscr {R} = \left \{ 1, 2, 3, 3 \right \}$.

我們選取元素 $P$ :

• 由於 $P < C_{2}$ 不成立, 所以更新 $\mathscr {R}$ 為 $\mathscr {R} = \left \{ 1, 2, 4, 3 \right \}$.

因此最終 $\mathscr {S}$ 中各個元素的名次為 $\mathscr {R} = \left \{ 1, 2, 4, 3 \right \}$.

$\blacksquare$

得到所有元素的名次之後, 對元素的排序就變得很簡單. 一個元素的名次是幾, 那麼就在新的集合中排在第幾個. 設排序之後的集合為 ${\mathscr {S}}' = \left \{ {e_{1}}', {e_{2}}', ..., {e_{n}}' \right \}$, 那麼 ${e_{R_{e_{i}}}}' = e_{i}$. 其中, $i = 1, 2, ..., n$.

我們合稱 Algorithm 1 和 Algorithm 2 為名次排序法 (ranking sort).

3. 原地重排的名次排序法

在 Algorithm 2 中, 我們為名次排序法創造了一個新的集合 ${\mathscr {S}}'$ 用於儲存排序結果, 排序完成之後原來的集合 $\mathscr {S}$ 就沒什麼用了. 那麼既然 $\mathscr {S}$ 沒什麼用了, 我們是否有可能在 $\mathscr {S}$ 上完成排序, 而不是在新的集合上排序呢?

我們計算得到元素的名次之後, 每一個元素的名次必定都是獨一無二的. 利用這個特點, 我們可以發現, 如果對於任意 $i$ ($i = 1, 2, ..., n$), 如果都有 $R_{e_{i}} = i$, 那麼說明集合就是有序的. 而對於 $R_{e_{i}} \neq i$ 的情況, 我們可以通過交換來讓 $R_{e_{i}} = i$ 成立. 例如現在位於第一個位置上的元素是 $e_{1}$, 但是 $R_{e_{1}} = j \neq 1$, 那麼我們就把元素 $e_{1}$ 和 $e_{j}$ 進行交換, 那麼就把 $e_{1}$ 放到了正確的位置上. 對於原來的 $e_{j}$ 來說, 如果 $R_{e_{j}} \neq 1$, 那麼就繼續交換. 直到第一個元素對應的名次是 $1$ 位置. 接下來的第二個第三個直到倒數第二個元素都這樣處理.

例題 2. 對集合 $\mathscr {S} = \left \{ B, C_{1}, P, A, C_{2}, K \right \}$ 及其名次 $\mathscr {R} = \left \{ 2, 3, 6, 1, 4, 5 \right \}$ 使用原地重排的名次排序法.

$解$ :

首先, $R_{B} = 2 \neq 1$, 但是 $B$ 在第一個位置上, 所以它應該和第 $R_{B} = 2$ 個元素進行交換, 得到 $\mathscr {S} = \left \{ C_{1}, B, P, A, C_{2}, K \right \}$ 和 $\mathscr {R} = \left \{ 3, 2, 6, 1, 4, 5 \right \}$. $R_{C_{1}} = 3 \neq 1$, 交換之後有 $\mathscr {S} = \left \{ P, B, C_{1}, A, C_{2}, K \right \}$ 和 $\mathscr {R} = \left \{ 6, 2, 3, 1, 4, 5 \right \}$. $R_{P} = 6 \neq 1$, 交換之後有 $\mathscr {S} = \left \{ K, B, C_{1}, A, C_{2}, P \right \}$ 和 $\mathscr {R} = \left \{ 5, 2, 3, 1, 4, 6 \right \}$. $R_{K} = 5 \neq 1$, 交換之後有 $\mathscr {S} = \left \{ C_{2}, B, C_{1}, A, K, P \right \}$ 和 $\mathscr {R} = \left \{ 4, 2, 3, 1, 5, 6 \right \}$. $R_{C_{2}} = 4 \neq 1$, 交換之後有 $\mathscr {S} = \left \{ A, B, C_{1}, C_{2}, K, P \right \}$ 和 $\mathscr {R} = \left \{ 1, 2, 3, 4, 5, 6 \right \}$.

接下來檢查 $R_{B}$, $R_{C_{1}}$, $R_{C_{2}}$, $R_{K}$ 和 $R_{P}$, 總有 $R_{e_{i}} = i$ ($i = 2, 3, 4, 5, 6$), 因此集合 $\mathscr {S}$ 有序.

$\blacksquare$

4. 複雜度分析

總體來說, 不論是否原地重排, 名次排序法的時間複雜度是 $\Theta(n^{2})$, 空間複雜度為 $\Theta(n)$. 針對名次排序法複雜度的具體分析可以見《複雜度分析實戰》, 此處不再累贅.

5. 實作

Code 1. 原地排序的名次排序法
#include <algorithm>

void ranking_sort(int array[], int size) {
    auto rank {new int[size] {}};
    for(auto i {1}; i < size; ++i) {
        for(auto j {0}; j < i; ++j) {
            if(array[j] > array[i]) {
                ++rank[j];
            }else {
                ++rank[i];
            }
        }
    }
    for(auto i {0}; i < size; ++i) {
        auto &save {rank[i]};
        while(save not_eq i) {
            std::swap(array[save], array[i]);
            std::swap(rank[save], save);
        }
    }
    delete[] rank;
}

對於泛型版本的實作, 大家可以參考我的 GitHub : https://github.com/Jonny0201/data_structure/blob/master/data_structure/algorithm.hpp, 搜尋 ranking_sort 即可.