## 定義
在生活中就有許多排序的例子，比如老師要求同學按照身高排隊，按照業績多寡評定優良員工等等
在程式中排序最重要的概念就是按照"特定條件"排好資料，在之後的演算法也可以看到排序的重要性
接下來就介紹幾種排序的做法，會從比較直覺(簡單)的做法到複雜的做法，資料都是 `a[0] ~ a[n-1]`
不過要強調，通常實作不需要自己寫排序演算法，而是寫前面說的"特定條件"，然後用 sort()
排序還有一個比較需要考慮的點，就是時間跟空間複雜度
因為在大量資料的時候，效率跟花費還是比較需要在意的
## 選擇排序法 (Selection Sort)
選擇排序就是找出還沒排序的目前最小值，然後將它移到前面
比如 $2,3,4,1$ 四個數字要用選擇排序，實際的作法就會像是下面這樣
最先找到最小值就是 $1$，把 $1$ 放到前面，會變成 $1,3,4,2$
再來還沒排序過的數字剩下 $3,4,2$，最小值是 $2$，把 $2$ 放到前面，變成 $2,4,3$
接著沒排序的數字剩下兩個 $4,3$，最小值是 $3$，把 $3$ 放到前面，變成 $3,4$
最後數字就會變成 $1,2,3,4$，就這樣排完了，概念講述結束，接下來換實作
```cpp=
void selection_sort(int n) {
for (int i=0;i<n-1;i++) { // 到 n-1 就可以了(因為最後一次排兩個數字)
int min_idx = i ; // 最小值的 index
for (int j=i+1;j<n;j++)
if (a[j] < a[min_idx]) // 更小的值
min_idx = j ;
if (min_idx != i) { // 交換數字位置
int tmp = a[min_idx] ;
a[min_idx] = a[i] ;
a[i] = tmp ;
}
}
}
```
跟前面的概念差不多，實作起來跟講解過程差不多
每次都花 $O(n)$ 的時間找最小值，找了 $n$ 次，時間複雜度是 $O(n^2)$
空間複雜度除了原有的陣列就是一些變數而已，所以是 $O(1)$
## 插入排序法 (Insertion Sort)
插入排序的概念比較像一排不同高度的積木分成兩組，一組是排好的一組是還沒排的
因為一開始都還沒排，所以排好的那組一開始沒有積木，當加入一個新的積木到排好的組別
就要將它插入到正確的位置，不過程式不是用插入，而是慢慢移過去，舉個例子
$4,2,3,1$ 用插入排序去做，那一開始就是先把 $4$ 移過去，沒排的剩下 $2,3,1$
$2,3,1$ 把 $2$ 移過去，排好的組別變成 $4,2$，沒排的剩下 $3,1$
這時候因為排好的組別順序不對，所以要將 $2$ 插到最前面變成 $2,4$
$3,1$ 把 $3$ 移過去，排好的組別變成 $2,4,3$，沒排的剩下 $1$
因為排好的組別順序不對，所以要將 $2$ 插到中間變成 $2,3,4$
把最後的 $1$ 移過去，排好的組別變成 $2,3,4,1$
因為順序不對，將 $1$ 插到最前面變成 $1,2,3,4$
實際的作法只是把插入的概念變成慢慢從右邊往左移到正確位置
```cpp=
void insertion_sort(int n) {
for (int i=0;i<n;i++) { // 需到 n (因為一次插一個數字)
// 注意分組，排好的組別是 a[0] ~ a[i-1]
// 需要插入的值是 a[i]，未排序的組別為 a[i+1] ~ a[n-1]
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 ; // 不須移動了，插入完畢
}
}
}
```
插入過程最多跑 $O(n)$，共插入 $n$，時間複雜度最壞為 $O(n^2)$
只有多了幾個變數，所以空間複雜度是 $O(1)$
## 泡沫排序法 (Bubble Sort)
泡沫排序法跟上面兩個不太一樣，但是也是滿簡單就能理解的排序法
最主要的方式就是重複做"相鄰兩元素，大的放右邊，小的放左邊，放相反就交換"
但是這樣其實還不夠明確，因為沒有一個條件能讓我們知道甚麼時候該停止重複
所以泡沫演算法需要從稍微推一下，假設一組測資 $3,5,1,2,4,7,9$ 這樣
如果從頭跑一次，$3,5$ 比較，不用交換，$5,1$ 比較，要交換，$5,2$ 比較....
透過這樣的方式，最後最大的數字會跑到最後方，那下次跑的時候就可以忽略最後方的元素
所以第一趟就排好最後一個元素，第二趟排好最後第二個元素，...，第 $n$ 趟排好第一個元素
實際上的程式碼會像是這樣
```cpp=
void bubble_sort(int n) {
for (int i=0;i<n;i++) {
for (int j=0;j<n-i-1;j++) { // 從最後一個、最後二個...
if (a[j+1] < a[j]) { // 比較並交換
int tmp = a[j] ;
a[j] = a[j+1] ;
a[j+1] = tmp ;
}
}
}
}
```
一次比較+交換跑 $O(n)$，共排了 $n$ 個元素，時間複雜度為 $O(n^2)$
只有多了幾個變數，所以空間複雜度是 $O(1)$
## 計數排序法（Counting Sort）
計數排序相較於前面的排序法差很多，因為前面都是用交換位置(對調)的概念
現在是用額外的空間去放數字，這個概念就是用空間換時間，也滿符合直覺的
計數排序法的實作很簡單，假設數字的範圍是 $0~K$，那我開一個大小 $K$ 的陣列
用來表示數字出現過幾次，最後在一次輸出所有的數字(出現過一次以上就照出現次數輸出)
```cpp=
void counting_sort(int n, int K) {
int cnt[K+1] ; // 數字範圍 0~K
for (int i=0;i<=K;i++) // 初始化
cnt[i] = 0 ;
for (int i=0;i<n;i++)
cnt[a[i]]++ ; // 元素出現的數量 + 1
int cur = 0 ; // 現在是 a 中的第幾個位置 (a 的 index)
for (int i=0;i<=K;i++)
while (cnt[i]--) // 剩餘出現數量 > 0
a[cur++] = i ; // 放置
}
```
計算元素出現次數 $O(n)$，依照出現次數放入陣列 $O(K)$，時間複雜度為 $O(n+K)$
需要多一個陣列儲存出現次數，所以空間複雜度是 $O(K)$
不過要注意的是，如果 $K$ 過大，空間跟時間的花費都會更多
## 穩定排序 or 不穩定排序
所謂穩定的排序，就是在排序使用的"特定條件"相同時，排序前後位置關係相同
如果以分數作為排序條件，原本 $90$ 分的小美排在 $90$ 分的小王上面
穩定的排序後小美依然在小王上面，反之不穩定的排序則兩者順序不一定
但其實只要在陣列內的元素，所有不穩定的排序都可以轉化成穩定的排序
最關鍵的地方就是在排序條件上，只要排序條件加上 index 就可以了
## 觀念總結
以上都是比較簡單的排序法，因為這篇主要是介紹排序的基礎概念，不會講太難的
另一方面排序本身都是搭配其他的演算法，純排序的概念用舉例的功效大於題目解說
如果再大部分的情況下，排序只需要用內建的 sort() 即可，通常需要寫的是排序條件
最後還是提供一些題目，來讓各位能夠用題目練習排序條件的做法
## 例題-ZJ m931. 1. 遊戲選角
[題目連結](https://zerojudge.tw/ShowProblem?problemid=m931)
解題思路 :
有 n 個角色，每個角色有攻擊力和防禦力。
角色的能力值是攻擊力和防禦力的平方和，輸出能力值第二大的攻擊力和防禦力數值。
保證每個角色的能力值相異。
這題其實只要用 "能力值" 作為排序條件，然後排序後第二大的就是答案了
```cpp=
#include<bits/stdc++.h>
using namespace std ;
typedef pair<int, int> Pii ;
#define FF first
#define SS second
bool cmp(Pii &x, Pii &y) { // 排序條件(能力值)
return x.FF*x.FF+x.SS*x.SS < y.FF*y.FF+y.SS*y.SS ;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0) ;
int n ;
cin >> n ;
vector<Pii> v(n) ;
for (int i=0;i<n;i++) // 輸入
cin >> v[i].FF >> v[i].SS ;
sort(v.begin(), v.end(), cmp) ; // 內建排序
cout << v[n-2].FF << ' ' << v[n-2].SS << '\n' ; // 第二大
return 0 ;
}
```
## 例題-ZJ d545. 2. 抽紙牌（poker）
[題目連結](https://zerojudge.tw/ShowProblem?problemid=d545)
解題思路:
這題比較不同的地方就是要一次儲存兩個參數，排序時也需要同時比較這兩個參數
這裡用 STL 的 pair，或是用 Tuple，不過我這裡用的是 struct
原本花色的比較需要將字元轉成能比較的數字，但因為剛好這四個英文字母順序跟花色大小相同
所以比較字元直接相當於比較花色，不需要再特別去轉換
然後還有一個需要做的就是先比較數字再比較花色，其實就是數字相同時才比較花色
```cpp=
#include<bits/stdc++.h>
using namespace std ;
struct card { // 一張卡兩個資料
char color ;
int num ;
} ;
card A[54] ;
bool cmp(card x, card y) { // 排序條件
if (x.num == y.num) // 數字一樣才比較
return x.color > y.color ; // 比較花色
return x.num > y.num ; // 比較數字
}
int main() {
ios::sync_with_stdio(0), cin.tie(0) ;
int n, m ;
cin >> n ;
for (int i=0;i<n;i++) // 輸入
cin >> A[i].color >> A[i].num ;
cin >> m ;
sort(A, A+n, cmp) ; // 排序
cout << A[m-1].color << ' ' << A[m-1].num << '\n' ;
// card ans = *nth_element(A, A+m-1, A+n, cmp) ;
// cout << ans.color << ' ' << ans.num << '\n' ;
return 0 ;
}
```
不過之前有說過 nth_element() 的用法，在這篇也可以用
就不需要用到 sort 了
## 例題-ZJ d150. 11369 - Shopaholic
[題目連結](https://zerojudge.tw/ShowProblem?problemid=d150)
解題思路 :
這題是買二送一，分次結帳看最多可以省多少，直覺看來，分最多次就是三個三個一組
至於三個三個應該怎麼分，可以從較小的情況開始討論，先從六個開始討論
直接拿隨便三個去結帳，其中最小的價格就是省下的錢，那想要省下的錢越多
就是要讓三個中最便宜的價格盡量更大，想當然另外兩個會更貴
所以在還沒結帳的商品內，選出價格最高的三個，價格第三高的就是買二送一省下來的錢
總結就是挑價格從大到小第 $3n$ 個的商品($n \ge 1$)
```cpp=
#include<bits/stdc++.h>
using namespace std ;
bool cmp(int &x, int &y) { // 由大到小排序
return x > y ;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0) ;
int t ;
cin >> t ;
while (t--) {
int n ;
cin >> n ;
vector<int> v(n) ;
for (int i=0;i<n;i++) // 輸入
cin >> v[i] ;
sort(v.begin(), v.end(), cmp) ; // 排序
int ans = 0 ;
// 從第 3 個(index 2)開始，三個三個數
for (int i=2;i<n;i+=3)
ans += v[i] ;
cout << ans << '\n' ;
}
return 0 ;
}
```
## 例題-ZJ b162. NOIP2007 1.統計數字
[題目連結](https://zerojudge.tw/ShowProblem?problemid=b162)
解題思路 :
計算不同數字的出現次數，這裡需要用到一個排序後的特性
簡單來說就是排序後相同的數字會放在一起，比如 $1,2,2,2,3,3,4,5,5,5,5$
那這時候從左到右跑，如果相鄰卻不同值表示遇到新的數字了
所以只要一邊紀錄目前數字出現幾次，一邊判斷是否需要更換數字
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0) ;
int n ;
cin >> n ;
vector<int> v(n) ;
for (int i=0;i<n;i++) // 輸入
cin >> v[i] ;
sort(v.begin(), v.end()) ; // 排序
int cnt = 1 ; // 數字出現次數
for (int i=1;i<n;i++, cnt++) { // 每次迴圈代表出現次數+1
if (v[i] != v[i-1]) { // 數字與之前不同
cout << v[i-1] << ' ' << cnt << '\n' ;
cnt = 0 ; // 更新數字出現次數
}
}
cout << v[n-1] << ' ' << cnt << '\n' ; // 輸出最後一個數字
return 0 ;
}
```
Sign in with Wallet
Connect another wallet