摘要訊息 : 利用元素的名次對元素進行排序.
0. 前言
名次在生活中非常常見, 看到名次, 大家可能第一時間就想起了大家在學校的時候, 成績的名次; 大家也可能想起對於某一類東西的評測名次... 要想有名次, 就必須有一個內容是可比較的, 也就必須有權的概念. 比如一個班裡的所有學生的名次, 以最終的成績為權, 然後進行名次排序 .
本篇文章中, 我們主要討論的是升序的名次排序法, 也就是從小到大對元素進行排序. 對於降序的情況, 類似可得.
更新紀錄 :
2022 年 4 月 21 日進行第一次更新和修正.
1. 排序的穩定性
任意給定一個元素集合 S \mathscr {S} S , 經過排序之後, 一個元素 e e e 在集合 S \mathscr {S} S 中的位置是第 k k k 位, k k k 的值是集合 S \mathscr {S} S 中比 e e e 小的元素的數量. 現在如果不限定集合 S \mathscr {S} S 的唯一性, 也就是集合 S \mathscr {S} S 中可以出現重複的元素, 那麼排序演算法 如何處理這些重複元素的順序關係到了一個排序演算法的穩定性 (stability).
定義 1. 設集合 S \mathscr {S} S 中存在重複元素, 任取兩個元素 e 1 ∈ S e_{1} \in \mathscr {S} e 1 ∈ S 和 e 2 ∈ S e_{2} \in \mathscr {S} e 2 ∈ S 滿足 e 1 = e 2 e_{1} = e_{2} e 1 = e 2 且 e 1 e_{1} e 1 在集合中的位置排在 e 2 e_{2} e 2 之前. 現在用某一演算法 A \mathbb {A} A 對集合 S \mathscr {S} S 中的元素進行排序. 若排序之後, e 1 e_{1} e 1 仍然在 e 2 e_{2} e 2 之前, 那麼我們說排序演算法 A \mathbb {A} A 是穩定的 (stable); 否則, 稱排序演算法 A \mathbb {A} A 是不穩定的 (unstable).
例如設有集合 S = { B , C 1 , P , A , C 2 , K } \mathscr {S} = \left \{ B, C_{1}, P, A, C_{2}, K \right \} S = { B , C 1 , P , A , C 2 , K } (C 1 C_{1} C 1 和 C 2 C_{2} C 2 在數值上相等, 下標僅用於區分在集合中的前後順序) 和排序演算法 A \mathbb {A} A . 使用 A \mathbb {A} A 對 S \mathscr {S} S 排序之後, 若有 S = { A , B , C 1 , C 2 , K , P } , \displaystyle {\mathscr {S} = \left \{ A, B, C_{1}, C_{2}, K, P \right \},} S = { A , B , C 1 , C 2 , K , P } , 那麼 A \mathbb {A} A 就是穩定的排序演算法; 若有 S = { A , B , C 2 , C 1 , K , P } , \displaystyle {\mathscr {S} = \left \{ A, B, C_{2}, C_{1}, K, P \right \},} S = { A , B , C 2 , C 1 , K , P } , 那麼 A \mathbb {A} A 就是不穩定的排序演算法.
2. 名次排序法
定義 2. 我們定義一個元素 e e e 在集合 S \mathscr {S} S 中的名次 R e R_{e} R e 為 R e = S 中所有小於 e 的元素數量 + S 中所有等於 e 且出現在其左側的元素數量 . \displaystyle {R_{e} = \mathscr {S} \text { 中所有小於 } e \text { 的元素數量} + \mathscr {S} \text { 中所有等於 } e \text { 且出現在其左側的元素數量}.} R e = S 中所有小於 e 的元素數量 + S 中所有等於 e 且出現在其左側的元素數量 .
名次排序法是按照集合中元素的名次對集合進行排序. 由定義 2 我們可以看出, 名次排序法是穩定的排序演算法.
為了進行名次排序法, 我們必須首先計算每一個元素的名次. 首先, 我們要配置額外 n n n 個空間用於儲存對應元素的名次. 然後任取 e i ∈ S e_{i} \in \mathscr {S} e i ∈ S , 比較剩餘元素和 e i e_{i} e i 的大小. 若 e i > e j e_{i} > e_{j} e i > e j , 那麼就讓儲存名次空間中的第 j j j 個元素增加一, 代表它的權重較大; 否則, 就讓儲存名次空間中的第 i i i 個元素增加一. 接下來排除 e i e_{i} e i , 然後再取一個元素, 將其與剩餘的元素作比較. 不斷重複上述步驟, 直到 S \mathscr {S} S 中只剩下一個元素為止. 其中, i , j = 1 , 2 , . . . , n , i ≠ j i, j = 1, 2, ..., n, i \neq j i , j = 1 , 2 , . . . , n , i = j .
Algorithm 1. 名次計算
例題 1. 計算集合 S = { B , C 1 , P , C 2 } \mathscr {S} = \left \{ B, C_{1}, P, C_{2} \right \} S = { B , C 1 , P , C 2 } 中各個元素的名次.
解 解 解 :我們令 R = { 1 , 1 , 1 , 1 } \mathscr {R} = \left \{ 1, 1, 1, 1 \right \} R = { 1 , 1 , 1 , 1 } . 其中, R \mathscr {R} R 中第 i i i 個元素表示 S \mathscr {S} S 中對應第 i i i 個元素的名次.
我們選取元素 B B B :
由於 B < C 1 B < C_{1} B < C 1 , 所以更新 R \mathscr {R} R 為 R = { 1 , 2 , 1 , 1 } \mathscr {R} = \left \{ 1, 2, 1, 1 \right \} R = { 1 , 2 , 1 , 1 } ; 由於 B < P B < P B < P , 所以更新 R \mathscr {R} R 為 R = { 1 , 2 , 2 , 1 } \mathscr {R} = \left \{ 1, 2, 2, 1 \right \} R = { 1 , 2 , 2 , 1 } ; 由於 B < C 2 B < C_{2} B < C 2 , 所以更新 R \mathscr {R} R 為 R = { 1 , 2 , 2 , 2 } \mathscr {R} = \left \{ 1, 2, 2, 2 \right \} R = { 1 , 2 , 2 , 2 } . 我們選取元素 C 1 C_{1} C 1 :
由於 C 1 < P C_{1} < P C 1 < P , 所以更新 R \mathscr {R} R 為 R = { 1 , 2 , 3 , 2 } \mathscr {R} = \left \{ 1, 2, 3, 2 \right \} R = { 1 , 2 , 3 , 2 } ; 由於 C 1 < C 2 C_{1} < C_{2} C 1 < C 2 不成立, 所以更新 R \mathscr {R} R 為 R = { 1 , 2 , 3 , 3 } \mathscr {R} = \left \{ 1, 2, 3, 3 \right \} R = { 1 , 2 , 3 , 3 } . 我們選取元素 P P P :
由於 P < C 2 P < C_{2} P < C 2 不成立, 所以更新 R \mathscr {R} R 為 R = { 1 , 2 , 4 , 3 } \mathscr {R} = \left \{ 1, 2, 4, 3 \right \} R = { 1 , 2 , 4 , 3 } . 因此最終 S \mathscr {S} S 中各個元素的名次為 R = { 1 , 2 , 4 , 3 } \mathscr {R} = \left \{ 1, 2, 4, 3 \right \} R = { 1 , 2 , 4 , 3 } .
■ \blacksquare ■
得到所有元素的名次之後, 對元素的排序就變得很簡單. 一個元素的名次是幾, 那麼就在新的集合中排在第幾個. 設排序之後的集合為 S ′ = { e 1 ′ , e 2 ′ , . . . , e n ′ } {\mathscr {S}}' = \left \{ {e_{1}}', {e_{2}}', ..., {e_{n}}' \right \} S ′ = { e 1 ′ , e 2 ′ , . . . , e n ′ } , 那麼 e R e i ′ = e i {e_{R_{e_{i}}}}' = e_{i} e R e i ′ = e i . 其中, i = 1 , 2 , . . . , n i = 1, 2, ..., n i = 1 , 2 , . . . , n .
Algorithm 2. 排序
我們合稱 Algorithm 1 和 Algorithm 2 為名次排序法 (ranking sort).
3. 原地重排的名次排序法
在 Algorithm 2 中, 我們為名次排序法創造了一個新的集合 S ′ {\mathscr {S}}' S ′ 用於儲存排序結果, 排序完成之後原來的集合 S \mathscr {S} S 就沒什麼用了. 那麼既然 S \mathscr {S} S 沒什麼用了, 我們是否有可能在 S \mathscr {S} S 上完成排序, 而不是在新的集合上排序呢?
我們計算得到元素的名次之後, 每一個元素的名次必定都是獨一無二的. 利用這個特點, 我們可以發現, 如果對於任意 i i i (i = 1 , 2 , . . . , n i = 1, 2, ..., n i = 1 , 2 , . . . , n ), 如果都有 R e i = i R_{e_{i}} = i R e i = i , 那麼說明集合就是有序的. 而對於 R e i ≠ i R_{e_{i}} \neq i R e i = i 的情況, 我們可以通過交換來讓 R e i = i R_{e_{i}} = i R e i = i 成立. 例如現在位於第一個位置上的元素是 e 1 e_{1} e 1 , 但是 R e 1 = j ≠ 1 R_{e_{1}} = j \neq 1 R e 1 = j = 1 , 那麼我們就把元素 e 1 e_{1} e 1 和 e j e_{j} e j 進行交換, 那麼就把 e 1 e_{1} e 1 放到了正確的位置上. 對於原來的 e j e_{j} e j 來說, 如果 R e j ≠ 1 R_{e_{j}} \neq 1 R e j = 1 , 那麼就繼續交換. 直到第一個元素對應的名次是 1 1 1 位置. 接下來的第二個第三個直到倒數第二個元素都這樣處理.
Algorithm 3. 原地重排的名次排序法
例題 2. 對集合 S = { B , C 1 , P , A , C 2 , K } \mathscr {S} = \left \{ B, C_{1}, P, A, C_{2}, K \right \} S = { B , C 1 , P , A , C 2 , K } 及其名次 R = { 2 , 3 , 6 , 1 , 4 , 5 } \mathscr {R} = \left \{ 2, 3, 6, 1, 4, 5 \right \} R = { 2 , 3 , 6 , 1 , 4 , 5 } 使用原地重排的名次排序法.
解 解 解 :首先, R B = 2 ≠ 1 R_{B} = 2 \neq 1 R B = 2 = 1 , 但是 B B B 在第一個位置上, 所以它應該和第 R B = 2 R_{B} = 2 R B = 2 個元素進行交換, 得到 S = { C 1 , B , P , A , C 2 , K } \mathscr {S} = \left \{ C_{1}, B, P, A, C_{2}, K \right \} S = { C 1 , B , P , A , C 2 , K } 和 R = { 3 , 2 , 6 , 1 , 4 , 5 } \mathscr {R} = \left \{ 3, 2, 6, 1, 4, 5 \right \} R = { 3 , 2 , 6 , 1 , 4 , 5 } . R C 1 = 3 ≠ 1 R_{C_{1}} = 3 \neq 1 R C 1 = 3 = 1 , 交換之後有 S = { P , B , C 1 , A , C 2 , K } \mathscr {S} = \left \{ P, B, C_{1}, A, C_{2}, K \right \} S = { P , B , C 1 , A , C 2 , K } 和 R = { 6 , 2 , 3 , 1 , 4 , 5 } \mathscr {R} = \left \{ 6, 2, 3, 1, 4, 5 \right \} R = { 6 , 2 , 3 , 1 , 4 , 5 } . R P = 6 ≠ 1 R_{P} = 6 \neq 1 R P = 6 = 1 , 交換之後有 S = { K , B , C 1 , A , C 2 , P } \mathscr {S} = \left \{ K, B, C_{1}, A, C_{2}, P \right \} S = { K , B , C 1 , A , C 2 , P } 和 R = { 5 , 2 , 3 , 1 , 4 , 6 } \mathscr {R} = \left \{ 5, 2, 3, 1, 4, 6 \right \} R = { 5 , 2 , 3 , 1 , 4 , 6 } . R K = 5 ≠ 1 R_{K} = 5 \neq 1 R K = 5 = 1 , 交換之後有 S = { C 2 , B , C 1 , A , K , P } \mathscr {S} = \left \{ C_{2}, B, C_{1}, A, K, P \right \} S = { C 2 , B , C 1 , A , K , P } 和 R = { 4 , 2 , 3 , 1 , 5 , 6 } \mathscr {R} = \left \{ 4, 2, 3, 1, 5, 6 \right \} R = { 4 , 2 , 3 , 1 , 5 , 6 } . R C 2 = 4 ≠ 1 R_{C_{2}} = 4 \neq 1 R C 2 = 4 = 1 , 交換之後有 S = { A , B , C 1 , C 2 , K , P } \mathscr {S} = \left \{ A, B, C_{1}, C_{2}, K, P \right \} S = { A , B , C 1 , C 2 , K , P } 和 R = { 1 , 2 , 3 , 4 , 5 , 6 } \mathscr {R} = \left \{ 1, 2, 3, 4, 5, 6 \right \} R = { 1 , 2 , 3 , 4 , 5 , 6 } .
接下來檢查 R B R_{B} R B , R C 1 R_{C_{1}} R C 1 , R C 2 R_{C_{2}} R C 2 , R K R_{K} R K 和 R P R_{P} R P , 總有 R e i = i R_{e_{i}} = i R e i = i (i = 2 , 3 , 4 , 5 , 6 i = 2, 3, 4, 5, 6 i = 2 , 3 , 4 , 5 , 6 ), 因此集合 S \mathscr {S} S 有序.
■ \blacksquare ■
4. 複雜度分析
總體來說, 不論是否原地重排, 名次排序法的時間複雜度是 Θ ( n 2 ) \Theta(n^{2}) Θ ( n 2 ) , 空間複雜度為 Θ ( n ) \Theta(n) Θ ( 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
即可.