排序的穩定與不穩定
如果一個排序法，在兩個元素的排列順序相等時，若有辦法按原本在陣列中的順序排列，就說它屬於穩定排序（stable）；若做不到，則屬於不穩定排序（unstable）。
對於一般整數而言，由於大小順序相同表示值完全相同，因此對調看不出影響；但規則一改，就可能有影響了。
例如按照先奇數再偶數的順序排列時，同是奇數的 \(3\) 和 \(7\)，它們的排列順序相等，但值不相等。
例如按照字串長度排序時，字串 abc 和 def 長度相同，因此排列順序相等，但它們相異。
如果 \(3, 7, 5, 2, 1, 4, 7\) 按照先奇數、後偶數的順序排序，由於所有奇數間的排列順序相同，所有偶數間的排列順序相同，結果應為 \(3, 7, 5, 1, 7, 2, 4\)。
有能力做到的，就是穩定排序；如果不能，就是不穩定排序。
哪些排序法穩定、哪些不穩定
目前提過的排序法，只有 Quick Sort 以及以它為核心的 intro sort 是不穩定的。
quick sort 屬於不穩定排序，基於 quick sort 的 intro sort 也是，
因此 C++ 內建的 sort 也屬於不穩定排序。
想想看，為什麼 quick sort 會屬於不穩定排序？
其它排序法又為何可以是穩定排序呢？
一個簡單的測試方法是讓 sort 的比較函式永遠只回傳 false，
如此一來所有元素的順序會完全相等，只要看排序前後順序是否一致，
就知道是不是穩定排序。
注意 intro sort 在 \(n\) 夠小時會直接使用 insertion sort，
而 insertion sort 屬於穩定排序，因此如果 \(n\) 不夠大，
可能測試不到 quick sort 導致誤以為 intro sort 是穩定排序。
需要穩定排序時怎麼辦
一般有兩種方向：
- 改用穩定的排序法，例如 merge sort
- break tie 使排序規則上不可能相等
- sort by index (sort by pointer)
- 將 element 和 index 用 struct 打包起來一起排
由於穩定和不穩定只在順序上相等時出現差異，如果元素間順序必定相異，那就沒有任何影響。
內建穩定排序 stable_sort
<algorithm> 提供另外一種選擇：stable_sort()，底層以 merge sort 實作，屬於穩定排序。
stable_sort(ary+i, ary+j+1);
用法和 sort() 基本相同。
打破平手 Break Tie
利用原本在序列中的 index 必定相異的特性，只要比較時有 index 參與就必定不會平手：
struct elem
{
string val;
int idx;
};
bool comp(const elem &p, const elem &q)
{
// 第一優先條件：字串長度，由小到大
if (p.val.size() != q.val.size())
{
return p.val.size() < q.val.size();
}
// 第二優先條件：元素原本的位置，由小到大
return p.idx < q.idx;
}
sort by index
sort by index 的概念是：保持序列原本順序不變，建立以 index 構成的新序列來排序。
如此不會破壞原資料的先後順序；原資料較大時，可以迴避大資料的搬動。在資料沒變動的前提下，能夠保留多種不同次序，不需每次對原資料重新排列。
const int N = 1005;
// 原資料
string str[N];
// index 序列
int idx[N];
// 對要排序的資料建立 index 序列
for (i=0; i<n; i++)
{
idx[i] = i;
}
// 對 index 序列 sort
sort(idx, idx+n, comp);
// 按排好的 index 序列來取出原本資料
for (i=0; i<n; i++)
{
j = idx[i];
cout << str[j] << "\n";
}
bool comp(const int &a, const int &b)
{
// 第一優先條件：字串長度，由小到大
if (str[a].size() != str[b].size())
{
return str[a].size() < str[b].size();
}
// 第二優先條件：在原序列中的 index，由小到大
return a < b;
}
歡樂練習時間
Kattis sidewayssorting - Sideways Sorting
Kattis sortofsorting - Sort of Sorting
VIP等級
你自製的網路遊戲 Ancient Plants Combat Saga（簡稱 APCS）上線後，
由於人氣爆發導致伺服器無法負荷，因此決定限制同時上線人數，
超過上限時需要排隊等候登入，而閒置太久的玩家則會被系統踹下線。
然而你不想讓身為衣食父母的課長們因排隊等待而棄坑，這將是筆大大的損失。
為此你建立了一套插隊系統，在遊戲內花過越多錢的，就能越早登入。
如果花一樣多錢，就遵守先來後到的規矩。
輸入先給一正整數 \(n\) 代表有多少個人正在排隊登入，
接下來 \(n\) 行每行有一串字串 \(S_i\) 和一個非負整數 \(M_i\)，
\(S_i\) 代表該帳號的 ID，只包含大小寫字母或數字，且長度不超過 \(15\)。
\(M_i\) 為該帳號總計付過多少錢。
依照登入順序輸出每個帳號的 ID，一個帳號一行。
\(1\le n\le 100000\)
\(0\le M_i\le 2,147,483,647\)
不會有任兩個帳號 ID 相同。
範例輸入
12
Marisa 100
Alice 2000
Yuugi 100
Sakuya 50000
Remilia 50000
Yuyuko 2000
Chiruno 9
Yuuka 0
Reimu 0
Furan 100
Suika 2000
Youmu 0
範例輸出
Sakuya
Remilia
Alice
Yuyuko
Suika
Marisa
Yuugi
Furan
Chiruno
Yuuka
Reimu
Youmu
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe