0%

0-13 排序

排序

其實這有點算是演算法的範圍,不過因為我認為排序對於基礎演算法、時間複雜度、分治、二分搜、常用函式等等主題來說,都是相當好的範例,因此,決定將其置於此。

這篇中,將會帶大家認識時間複雜度的概念、以泡沫排序介紹演算法、使用預設的sort函式及自定義比較函式。進階的排序方法與逆序數對等主題,將會於下一本書中介紹。

排序是什麼

把一堆東西,按照某個特定的規則排好。例如:由小排到大或由大排到小等等。

來看一下這個題目:

ZeroJudge a104

1
2
3
4
5
有多筆測資以EOF為結束

第一行有一個正整數n(1<=n<=1000),代表有幾個數字要請你幫忙排

第二行有n個可以用int儲存的正整數

假設輸入是:

1
1 3 2 4 5

你當然可以說,那我把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
// ZJ a104 selection sort
#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。

1
sort(arr+1, arr+1+N);

這樣,就sort好了。更棒的是,它的時間複雜度是 $O(NlogN)$。因此,就順利的通過了這題。

sort函式中,需要傳入兩個參數:開始與結束位置。而由於採用左閉右開(左界包含,右界不含)的設計,開始位置是有放東西的第一格,結束位置是最後一個有放東西的位置的下一格

假設現在我有長度為 4 的陣列 arr,並從 1 開始放了 3 個數字在 arr[1], arr[2], arr[3] 的位置,那在 sort 時,就寫:

1
2
sort(arr+1, arr+4);
// 開始 結束

假設我從 0 開始,放在 arr[0], arr[1], arr[2],那在 sort 時,就寫:

1
sort(arr, arr+3)

那如果我從 1 開始放,放 N 個,當然就是這樣寫啦:

1
sort(arr+1, arr+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
// ZJ a104 selection sort
#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
// ZJ a104 bubble sort

#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
// ZJ a233
#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
// ZJ a915 struct
#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
// ZJ a915 no struct
#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
//TOJ 15
#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"; // first char of their work

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
// TOJ 539
#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
// ZJ c471
#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];
// 如果 f[a] * w[b] > f[b] * w[a],那麼 a 一定會排在 b 的上面,否則交換 a, b 後,答案會更小
}

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
// TOJ 11 關鍵字:逆序數對/ counting inversion
#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++]; // tmp[id] = arr[lid], id++, lid++;
else tmp[id++] = arr[rid++], ans += m+1-lid;
}
while(lid <= m) tmp[id++] = arr[lid++];// tmp[id] = arr[lid], id++, 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';
}
}