日常生活中，排序的例子隨處可見。想像你今天被老師指派幫忙收全班的考卷，而老師為了方便，還請你幫忙把考卷照大家的座號從小到大排好，這時候你會怎麼做呢？如果全班只有 40 個人倒還好，但如果你得處理全校 800 個人的考卷呢？
這種將一堆資料「從小到大」排好的動作就稱作「排序」，而當資料量龐大的時候，排序演算法的重要性就出現了。由於排序實在是太常用到，也會有各種千奇百怪的場合需要應用，也因此資訊科學家們會設計出各式各樣的排序演算法。
以下我們就來一一介紹，並假設資料們存在 a[1] 到 a[n] 之間。
選擇排序法在做的事情非常直觀：每次找到座號最小的考卷，把他放在前面。
寫成程式碼會是什麼樣子的呢？
void selection_sort(int a[], int n) {
for (int i = 1; i < n; ++i) {
// 欲選出第 i 小的元素，此時 a[i]~a[n] 還沒排序好
int min_pos = i; // 預設 a[i] 是最小的數字
for (int j = i + 1; j <= n; ++j) {
if (a[min_pos] > a[j]) {
// 發現更小的數字
min_pos = j;
}
}
if (min_pos != i) {
// 交換兩個位置上的數字
int tmp = a[min_pos];
a[min_pos] = a[i];
a[i] = tmp;
}
}
}由於需要找 $n$ 次最小的數字，每次花 $O(n)$ 找到最小的數字在哪，所以是 $O(n^2)$。
頂多額外開幾個變數而已，因此是 $O(1)$。
插入排序法的想法也是另一方面的直觀：不妨一張一張考卷拿進來排好，每次拿一張考卷進來時插入到定位就好！
寫成程式碼會是什麼樣子的呢？
void insertion_sort(int a[], int n) {
for (int i = 1; i <= n; ++i) {
// 欲插入第 i 個數字，此時 a[1]~a[i-1] 已經排序好了
/* 注意到此時，第 i 個數字在 a[i]，因此我們可以先檢查 a[i] 跟 a[i-1] 的順序
是不是相反的，若相反則交換兩個數字，再檢查 a[i-1] 和 a[i-2]......
直到順序正常，就可以停止了 */
for (int j = i; j > 1; --j) {
if (a[j - 1] > a[j]) {
// 順序相反，需要交換兩個位置上的數字
int tmp = a[j - 1];
a[j - 1] = a[j];
a[j] = tmp;
}
else {
// 順序正確，數字已插入到定位
break;
}
}
}
}由於需要插入 $n$ 個數字，每次最慘花 $O(n)$ 將數字換到最底部，所以最差是 $O(n^2)$。
但最好的情況下，可能每次插入都跑沒多久就停了，例如在序列本身就已經排序好的情況下插入排序法的時間複雜度可以達到 $O(n)$！
頂多額外開幾個變數而已，因此是 $O(1)$。
泡沫排序法的想法比上面兩個稍微特殊一點，他不斷檢查序列中是否有「相鄰順序相反」的兩個數字，如果有，就把他們交換，重複執行直到找不到這樣的相鄰對為止。
直接看程式碼可能會比較清楚：
void bubble_sort(int a[], int n) {
for (int i = 1; i < n; ++i) {
// 循環 n-1 遍
for (int j = 1; j < n - i + 1; ++j) {
if (a[j] > a[j + 1]) {
// 順序相反，需要交換兩個位置上的數字
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
}
}
}這裡程式碼可能會有幾個不好懂的地方，首先是為什麼只需要循環 $n-1$ 遍呢？理由是因為每次循環過一遍之後，可以想像最大的數字肯定會跑到序列的最後面，也因此第二遍循環可以當作只需要排序 a[1] 到 a[n-1]；第三遍就只需要排序 a[1] 到 a[n-2]……，而到了第 $n-1$ 個循環結束後，只剩下 a[1] 需要排序，一個元素當然直接就排好，整個排序演算法也就結束了。
這同時也解釋了為什麼第 $i$ 次循環我們只考慮 a[1] 到 a[n-i+1]，也就是上述程式碼第 4 行的終止條件。
那為什麼他叫做泡沫排序法呢？緣由是命名者認為數字們會經由交換慢慢的「浮」到序列正確的位置XD
由於循環 $n-1$ 次，每次花費 $O(n)$ 掃視過一遍整個序列，因此是 $O(n^2)$。
頂多額外開幾個變數而已，因此是 $O(1)$。
計數排序法的想法特別單純，如果我要排的資料都是介在 $0\sim C$ 之間的數字，那是不是直接數每個數字有幾個，再一口氣掃過 $0\sim C$ 把對應的數字個數印出來就好了？
直接來看看程式碼會是什麼樣子的：
void counting_sort(int a[], int n) {
static int cnt[C + 1]; // 計數用的陣列
for (int i = 1; i <= n; ++i) {
++cnt[a[i]];
}
int current = 0; // 現在排到第幾個位置
for (int i = 0; i <= C; ++i)
while (cnt[i] > 0) {
// 這個數字還有剩
a[++current] = i;
--cnt[i];
}
}從 $0$ 往上掃到 $C$ 的過程中，每次看 cnt[i] 有多少，推對應這麼多個數字回原陣列就好了！
每個數字都只需要計數一次，接下來就是遍歷所有的數字一遍後按照個數推入數字，因此是 $O(n+C)$。
這次我們需要一個額外計數的陣列，因此是 $O(C)$。
如果讀者已經了解過「前綴和」這個技巧的意義的話，可以參考看看計數排序法一個很有趣的應用。
一般的計數排序法只排序「數字」，但回到排序考卷的狀況，每張考卷可不是只有分數，還有名字，總不能草草把「分數的數字們」排序好就交給老師吧？名字也必須跟著分數走！
這種雖然是排序數字但每個數字又「攜帶著一些額外物件」的問題同樣還是能用計數排序法解決，想法是預先知道「每個數字的尾端」會在哪裡，再倒著把他們從這個尾端放回來就好。而這個「尾端」，其實就是小於等於自己數字的所有數字出現次數，也因此只需要一個前綴和就能搞定。
struct Data {
int key;
Custom_Type something_else;
};
void advance_counting_sort(Data a[], int n) {
static int cnt[C + 1]; // 計數用的陣列
static Data result[N + 1];
for (int i = 1; i <= n; ++i) // 計數
++cnt[a[i].key];
for (int i = 1; i <= C; ++i) // 前綴和
cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; --i) // 從每個數字的尾端開始往前放
result[cnt[a[i].key]--] = a[i];
for (int i = 1; i <= n; ++i)
a[i] = result[i];
for (int i = 0; i <= C; ++i) // 清空計數陣列
cnt[i] = 0;
}至於為何刻意要從尾端倒著放回來，相信讀者可以從上述的實作感受到他的簡潔性。
考卷的分數大多數都落在 $0\sim 99$ 之間，如果先對十位數排序，每個十位數內部是不是就省事多了呢？
但倘若今天分數介在 $0\sim 999$ 之間，這時候先對百位數排序、每個百位數內部又要對十位數排序、每個內部的十位數又要對個位數排序……那 $0\sim 9999$ 呢？如果有 $k$ 位數呢？
好像越來越麻煩了！基數排序法的想法雖然是從這裡出發，但他換了個角度思考——不妨我們先對個位數排序、再對十位數排序……最後才對最大的第 $k$ 個位數排序。
聽起來有點奇怪？讓我們直接看程式碼。
void radix_sort(int a[], int n) {
static int radix[10][N + 1], radix_cnt[10];
int ten = 1;
for (int i = 0; i < k; ++i) {
// 對第 i 個位數排序
for (int j = 0; j < 10; ++j) {
// 重設每個存數字陣列的計數器
radix_cnt[j] = 0;
}
for (int j = 1; j <= n; ++j) {
// a[j] 除以 10 的 i 次方後，除以 10 的餘數就是第 i 個位數的值
int number = a[j] / ten % 10;
radix[number][++radix_cnt[number]] = a[j];
}
int current = 0;
for (int j = 0; j < 10; ++j) {
// 把第 i 個位數是 j 的數字拿出來
for (int t = 1; t <= radix_cnt[j]; ++t) {
a[++current] = radix[j][t];
}
}
// 刻意維護 ten，讓 ten 在第 i 輪的時候是 10 的 i 次方
ten *= 10;
}
}讓我們想像兩位數的情況
radix 裡面的radix[j] 內部的數字，順序上也會是照著個位數排好的！同樣的情況可以推廣到共 $k$ 個位數，這裡就交給讀者多想一下了。
當最大的數不超過 $10^k$ 時，總共排 $k$ 輪，每次 $O(n)$，因此總共的時間複雜度為 $O(k\cdot n)$。
由於需要開 $10$ 條陣列用來存數字，因此空間複雜度為 $O(10n)$。當然，在複雜度的世界裡，常數是可以省略的，所以我們也可以說是 $O(n)$；或更精確的說，若採用 $p$ 進位系統，則空間複雜度為 $O(p\cdot n)$。
如果搭配計數排序法中的進階使用方法，其實可以讓基數排序法的程式碼更加精簡！空間上可以從原本的 $O(p\cdot n)$ 降至 $O(p + n)$，也可以獲得時間上不少的常數優化，供讀者自行練習。
在眾多的排序演算法中，有一種分類方式叫做「穩定」，有些排序演算法會被分類成穩定的，有些則會被分類成不穩定的。
具體來說是什麼意思呢？先看定義。
假設我們今天排序這三張考卷：$\{(80, 小美), (80, 小智), (60, 小明)\}$。
這時候，單純對分數的排序結果有可能是以下兩種：
這是因為我們在「比較兩筆資料」時只比較分數，所以同樣分數的人自然就有多種不同的結果。
而能夠保證同樣分數的人在排序後依舊保持著原本輸入順序的演算法，就被稱為「穩定排序演算法」。
我們上述的五個演算法，若要分類的話就是
讀者可以試著複習一下每個演算法，看看他們是不是真的符合上述的分類。
不過實際上，穩不穩定還是全看實作之後的樣子，就好比如果我們讓犧牲額外 $O(n)$ 的空間來讓選擇排序法可以放數字在新的地方的話，就可以保持順序了；好比如果計數排序法的「進階使用方法」中，倒數第二個迴圈不要倒著跑，那最終的結果就不能保持順序了！（實際上同樣 key 值的資料會反過來排）
仔細一看上述五個演算法，後兩個（計數、基數）好像都是利用數字的特性在排序的？這樣會不會感覺有點偷吃步啊？
實際上資訊科學家為了分辨真正能夠推廣到最一般情況的排序問題，便給出了一個最一般的限制：我們只能透過不斷詢問兩筆資料的大小關係來進行排序！
舉個例子，常常有的時候很多資料是無法被數值化的，但兩兩擺在一起卻又好像分得出優劣，就好像現在有好多家火鍋店，可能問你兩家，你大概能夠分得出你比較喜歡吃哪一家，但要你全部幫他們打分數，又變得好困難。這時候如果要將這些火鍋店按照你的喜好從最不喜歡到最喜歡排好的話，也只能兩家兩家問了。
也因此，排序演算法們又可以被分類成「是否基於比較」的兩種。當然，上述五個演算法的分類就是
關於比較這件事，我們會在之後的章節講得更清楚一些。
實際上，讀者如果上網去維基百科等地方查詢排序演算法，應該可以找到更多不同種類的排序演算法，筆者這裡介紹的只不過是最常用的幾種罷了。甚至因為排序實在是太經典的問題，還會有人為了有趣設計像是臭皮匠排序這種有趣的排序演算法。
不過，也是因為排序太常用了，所以在比賽中我們通常都不用自己寫排序演算法，而是直接 call 內建可以在 $O(n\log n)$ 的時間內排好 $n$ 筆資料的函式 std::sort。我們會在未來的章節介紹他的用法。
咦？那我們學上面那些 $O(n^2)$ 的演算法幹嘛？可能在遙遠的未來，就會知道了……
如果想要更了解上面那些演算法，可以看看下面這些補充影片