排序
其實這有點算是演算法的範圍，不過因為我認為排序對於基礎演算法、時間複雜度、分治、二分搜、常用函式等等主題來說，都是相當好的範例，因此，決定將其置於此。
這篇中，將會帶大家認識時間複雜度的概念、以泡沫排序介紹演算法、使用預設的sort函式及自定義比較函式。進階的排序方法與逆序數對等主題，將會於下一本書中介紹。
排序是什麼
把一堆東西，按照某個特定的規則排好。例如：由小排到大或由大排到小等等。
來看一下這個題目：
ZeroJudge a104
1
2
3
4
5
| 有多筆測資以EOF為結束
第一行有一個正整數n(1<=n<=1000)，代表有幾個數字要請你幫忙排
第二行有n個可以用int儲存的正整數
|
假設輸入是：
你當然可以說，那我把2、3交換位置，就排好了。
但是今天，程式要做的，是對於所有在限制範圍內的輸入，都要能夠在限制時間內，輸出正確解答。也就是說，要有一個通解程式！
而這，就是演算法的基本概念，演算法，就是解決問題的方法。
直接將輸入原封不動的輸出，對於特定測試資料(例如：本來就已經排好)的輸出答案會是正確的，但它並不會對於所有輸入都能夠產生正確解答。這也是為什麼你的程式常常能夠通過範例測試，但卻在 Online Judge 上一直 WA 的原因。因為你的程式通過範例只是運氣好，它沒有辦法對任意輸入都輸出正確解。
思考一下吧
先想個三分鐘，想想看如何運用簡單的陣列、迴圈，寫出針對上題的排序演算法吧！
範例程式碼會在最下方提供。這裡，我想提供兩種想法。
1. 選擇排序法(Selection Sort)
每次找到陣列中最小的值，將其放入新的陣列後，從原本的陣列移除，若原陣列長度為 N，重複執行 N 次後，當所有的元素都從原本的陣列移除後，我們就排序好了！
但其實，我們不用開新的陣列，只需要在第 i 次執行時，將找到的那個值，換到第 i 個位置。在下一次尋找時，從 i+1 位置開始尋找就好，可以省下約兩倍的時間與空間。
選擇排序法圖解
2. 泡沫排序法
不停的掃過整條陣列，當發現左邊的數字比右邊的還要大的時候，就交換兩數，直到再也找不到這樣的數字為止。
但實作上有個優化，每次從左往右掃，並交換需要交換的數字。先看位置 1 是否比位置 2 大，如果是的話就交換，再看 2 跟 3，3 跟 4，……最後看 N-1 跟 N。
可以發現，在從左往右掃完一次陣列時，最大的數字，一定可以成功被換到最右邊。所以第二次時，就只需考慮 1 ~ N-1 的陣列了。從左往右掃完第二次陣列時，第二大的數字，就會成功被換到 N-1 的位置。
就這樣執行 N (其實是N-1) 次後，陣列就順利排序好了！
泡沫排序法圖解
複雜度
在 AC 了剛剛那一題後(請先 AC 上面那一題再繼續看下去)，拿原本的 code 傳這一題看看：
ZeroJudge a223
奇怪，怎麼 TLE 了？
這應該是你遇到的第 2、3 個 TLE，前面的章節的練習裡，會出現 TLE 的原因是什麼呢？
啊！對了！是輸入太慢！
於是，你加上輸入優化，但還是沒過。為什麼呢？
這裡，來稍微介紹一下複雜度的概念。複雜度，就是你的程式在最差情況下，會執行多少次基本操作。
什麼是基本操作呢？
1
2
3
4
5
| a++;
b--;
c*=5;
a+=9*45/7;
a[1] = a[0];
|
這些只需要一步就能完成的動作，我們叫它基本操作。其實，非基本操作好像都還沒出現在這本講義~
電腦一秒鐘能執行的基本動作數量，大約是 $10^8$ 左右。這下，明白為什麼題目要設置時間限制了嗎？
演算法不僅要正確，速度也是很重要的！
現在，我們就試著分析一下選擇排序法的複雜度。
選擇排序法的主要概念，便是重複 N 次找最大值的過程。在每一次的過程中，程式需要去遍歷整個陣列。那麼，基本操作在哪裡？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include<bits/stdc++.h>
using namespace std;
int n, arr[1005];
int main(){
while(cin >> n){
for(int i=1;i<=n;i++) cin >> arr[i];
for(int i=1;i<=n;i++){
int mn = arr[i], id = i;
for(int j=i+1;j<=n;j++){
if(arr[j] < mn) id = j, mn = arr[j];
}
swap(arr[i], arr[id]);
}
for(int i=1;i<=n;i++){
cout << arr[i];
if(i < n) cout<<" ";
else cout<<'\n';
}
}
}
|
j++，arr[j] < mn，swap(arr[i], arr[id])，這些全部都是基本操作。其中，前兩個基本操作，在第 i 回合時，都會執行到 N-i 次。因此，我們知道，j++ 總共被執行的數量，應該是 1 + 2 + 3 + 4…… + N-1 = (N) * (N-1) / 2 次。
在 N = 1000，也就是上題的限制時，總共約需要執行 500000 次的 j++，但電腦一秒可以跑 $10^8$ 次，因此能夠順利通過前一題。
但在本題的最大範圍： N = 1000000 下，總共約需要執行 $5 \times 10^{11}$ 次 j++，因此，光是 j++ 這個動作，電腦就需要花上 5000 秒，想當然，這就是 TLE 的原因。
$O(N)$? $O(N^2)$?
但要是我們將所有基本操作都列入計算，例如：i++ 執行 N 次，if(arr[j] > mx)執行 N * (N-1) / 2 次，可能光算出來就花很久了，而且，我們也不需要那麼精密的計算，估個大概就好。
因此，我們捨棄所有跟題目限制沒有關係的常數，以最高次項為代表。
假設算出來程式會執行 $2 \times N^2 + 60 \times N + 7895$ 次，我們就直接捨棄 $N^2$ 以外的東西，畢竟，在 N 高達數千、甚至數萬的情況下，$60 \times N$ 再怎麼大，都遠小於 $N^2$，因此在估算上，直接捨去就好。
所以，要是一個演算法的最高次項是 $N^2$，我們就會說： 這是一個 $O(N^2)$ 的演算法
$O(N)$這個符號，其實是有嚴格的定義的，有興趣的可以點這裡，不過這邊就容我略過了。
sort函式
知道時間複雜度的概念以後，應該可以知道TLE的原因了吧！那，要如何通過這題呢？顯然我們需要一個比 $O(N^2)$ 還要快的排序演算法。
排序演算法在極限情況下，可以在 $O(NlogN)$ 的時間內完成排序工作。常見的 $O(NlogN)$ 排序有 quick sort 以及 merge sort 等等。但由於其概念較難懂，將放至下一本說明，有興趣的話可以點進連結。
這裡要介紹的，是 C++ 內建的函式：sort。
這樣，就sort好了。更棒的是，它的時間複雜度是 $O(NlogN)$。因此，就順利的通過了這題。
sort函式中，需要傳入兩個參數：開始與結束位置。而由於採用左閉右開(左界包含，右界不含)的設計，開始位置是有放東西的第一格，結束位置是最後一個有放東西的位置的下一格。
假設現在我有長度為 4 的陣列 arr，並從 1 開始放了 3 個數字在 arr[1], arr[2], arr[3] 的位置，那在 sort 時，就寫：
假設我從 0 開始，放在 arr[0], arr[1], arr[2]，那在 sort 時，就寫：
那如果我從 1 開始放，放 N 個，當然就是這樣寫啦：
這行執行完後，你就會神奇的發現，陣列排序好了！
自定義比較函式
sort 預設是由小排到大。那如果我現在要由大排到小，要怎麼做呢？
sort 隱藏的第三個參數，是比較函式。若在排序後的陣列中 A 必定要置於 B 之前，那麼此函式在接收到 A, B 時，必須回傳 true。否則回傳 false。
範例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include<bits/stdc++.h>
using namespace std;
int n, arr[1000005];
bool cmp(int a,int b){
return a > b;
}
int main(){
cin >> n;
for(int i=1;i<=n;i++) cin >> arr[i];
sort(arr+1, arr+1+n, cmp);
for(int i=1;i<=n;i++) cout << arr[i] << " ";
}
|
注意的一點是，回傳 true 的條件是，A 必定要置於 B 之前。因此若 A == B，是不可以回傳 true 的。回傳 true 的話，由於不管傳入 (A, B) 或是 (B, A) 都回傳 true，程式會停不下來，通常會導致 Runtime Error 的結果。
不單純的 sort
來看看這題：
ZeroJudge a915
(請自動忽略簡體字)
1
| 給你 n 個二維平面上的點，要求你把他們按照以x軸坐標為第一關鍵字，y軸坐標為第二關鍵字的方式從小到大來進行排序。
|
也就是說，先比 x，x 一樣的話再比 y。
二維平面上的點是由兩個整數組成，要怎麼將兩個整數合起來視為一個點？如果將 x 跟 y 分開存，sort 後不是會跑掉嗎？
所以，我們使用上一節教的 struct。
1
2
3
4
5
| struct Point{
int x, y;
};
Point arr[1005];
|
那要怎麼 sort 呢？要 sort 的條件是，必須要有 < 這個運算子，這樣程式才知道怎麼排嘛。還記得上一節教的定義運算子嗎？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| struct Point{
int x, y;
bool operator<(Point b){
if(x != b.x) return x < b.x;
else return y < b.y;
}
};
Point arr[1005];
int n;
int main(){
cin >> n;
for(int i=1;i<=n;i++){
cin >> arr[i].x >> arr[i].y;
}
sort(arr+1, arr+1+n);
}
|
這樣，就可以使用 sort 了。
另一種方法
如果將 x 跟 y 分開存，能 sort 嗎？
當然，只是我們不能對存他們的陣列 sort，但是我們可以另外開一個裡面是 1~N 的陣列，代表他們的位置。接著，透過自定義比較函式，比較 a 與 b 時，我們就比較 x[a] 跟 x[b] 誰比較小，如果一樣的話再比 y[a] 跟 y[b]，這樣 sort 出來的陣列，就是他們由小排到大的順序了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<bits/stdc++.h>
using namespace std;
int x[1005], y[1005], idx[1005], n;
bool cmp(int a, int b){
if(x[a] != x[b]) return x[a] < x[b];
else return y[a] < y[b];
}
int main(){
cin >> n;
for(int i=1;i<=n;i++){
cin >> x[i] >> y[i];
idx[i] = i;
}
sort(idx+1, idx+1+n, cmp);
for(int i=1;i<=n;i++){
cout << x[idx[i]] << " " << y[idx[i]] << '\n';
}
}
|
內建這麼好用，全部都用內建的 sort 就好啦
恩，你先寫寫看例題吧。
例題
ZeroJudge a104
ZeroJudge a233
ZeroJudge a915
★★ TOJ 15
★★★ TOJ 539
★★★★ ZeroJudge 471
Hint: 找到 A 必定要置於 B 之前的條件
★★★★★ TOJ 11
Hint: 如果我只要問：最小的數字在這過程中，會需要交換幾次呢？
AC code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include<bits/stdc++.h>
using namespace std;
int n, arr[1005];
int main(){
while(cin >> n){
for(int i=1;i<=n;i++) cin >> arr[i];
for(int i=1;i<=n;i++){
int mn = arr[i], id = i;
for(int j=i+1;j<=n;j++){
if(arr[j] < mn) id = j, mn = arr[j];
}
swap(arr[i], arr[id]);
}
for(int i=1;i<=n;i++){
cout << arr[i];
if(i < n) cout<<" ";
else cout<<'\n';
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include<bits/stdc++.h>
using namespace std;
int n, arr[1005];
int main(){
while(cin >> n){
for(int i=1;i<=n;i++) cin >> arr[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=n-i;j++){
if(arr[j] > arr[j+1]) swap(arr[j], arr[j+1]);
}
}
for(int i=1;i<=n;i++){
cout << arr[i];
if(i < n) cout<<" ";
else cout<<'\n';
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include<bits/stdc++.h>
using namespace std;
int n, arr[1000005];
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i=1;i<=n;i++) cin >> arr[i];
sort(arr+1, arr+1+n);
for(int i=1;i<=n;i++){
cout << arr[i];
if(i < n) cout << " ";
else cout << '\n';
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include<bits/stdc++.h>
using namespace std;
struct Point{
int x, y;
bool operator<(Point b){
if(x != b.x) return x < b.x;
else return y < b.y;
}
};
Point arr[1005];
int n;
int main(){
cin >> n;
for(int i=1;i<=n;i++){
cin >> arr[i].x >> arr[i].y;
}
sort(arr+1, arr+1+n);
for(int i=1;i<=n;i++){
cout << arr[i].x << " " << arr[i].y << '\n';
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include<bits/stdc++.h>
using namespace std;
int x[1005], y[1005], idx[1005], n;
bool cmp(int a, int b){
if(x[a] != x[b]) return x[a] < x[b];
else return y[a] < y[b];
}
int main(){
cin >> n;
for(int i=1;i<=n;i++){
cin >> x[i] >> y[i];
idx[i] = i;
}
sort(idx+1, idx+1+n, cmp);
for(int i=1;i<=n;i++){
cout << x[idx[i]] << " " << y[idx[i]] << '\n';
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include<bits/stdc++.h>
using namespace std;
struct cat{
int rk, age;
string name;
bool operator<(cat b){
if(rk != b.rk) return rk < b.rk;
else if(age != b.age){
if(rk == 5) return age < b.age;
else return age > b.age;
}
else return name < b.name;
}
};
cat arr[10005];
int n, m;
string ord = " enkwamdl";
int main(){
ios::sync_with_stdio(0), cin.tie(0);
while(cin >> n >> m){
for(int i=1,age;i<=n;i++){
string name, work;
cin >> name >> work >> age;
for(int j=1;j<=8;j++){
if(work[0] == ord[j]){
arr[i] = {j, age, name};
}
}
}
sort(arr+1, arr+1+n);
if(n < m) m = n;
for(int i=1;i<=m;i++){
cout << arr[i].name << '\n';
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n, k, arr[200005][2], dif[200005];
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> k;
ll tot = 0;
for(int i=1;i<=n;i++) cin >> arr[i][0];
for(int i=1;i<=n;i++) cin >> arr[i][1], tot += arr[i][1];
for(int i=1;i<=n;i++) dif[i] = arr[i][1] - arr[i][0];
sort(dif+1, dif+1+n);
for(int i=1;i<=n;i++){
if(tot - dif[i] < k){
cout << i-1 << '\n';
return 0;
}
tot -= dif[i];
}
cout << n << '\n';
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n, w[100005], f[100005], id[100005];
bool cmp(int a,int b){
return f[a] * w[b] > f[b] * w[a];
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i=1;i<=n;i++) cin >> w[i];
for(int i=1;i<=n;i++) cin >> f[i], id[i] = i;
sort(id+1, id+1+n, cmp);
ll top = 0, ans = 0;
for(int i=1;i<=n;i++){
ans += top * f[id[i]];
top += w[id[i]];
}
cout << ans << '\n';
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int arr[2000005], tmp[2000005], n;
ll ans;
void merge_sort(int l, int r){
if(l == r) return;
int m = (l+r)/2;
merge_sort(l, m);
merge_sort(m+1, r);
int lid = l, rid = m+1, id = l;
while(lid <= m && rid <= r){
if(arr[lid] <= arr[rid]) tmp[id++] = arr[lid++];
else tmp[id++] = arr[rid++], ans += m+1-lid;
}
while(lid <= m) tmp[id++] = arr[lid++];
while(rid <= r) tmp[id++] = arr[rid++];
for(int i=l;i<=r;i++) arr[i] = tmp[i];
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
while(cin>>n){
ans = 0;
for(int i=1;i<=n;i++) cin >> arr[i];
merge_sort(1, n);
cout << ans << '\n';
}
}
|