che's blog
0%

排序法整理-2023個人用教材

Posted on In
Symbols count in article: 1.7k Reading time ≈ 6 mins.
sort整理(bubble, selection, quick, merge, inserrtion sort)

排序

常見排序法

排序前必要條件:
所有值必須丟到一個array或vector裡

1. 泡沫排序法 (bubble sort)

基本上就是兩層迴圈下去跑，只要前面的比後面大就交換。

時間複雜度 O(n²)

基本架構:

1
2
3
4
5
6
7
for(int i=0;i<n-1;i++) {
    for (int j=0;j<n-i-1;j++) {
        if (arr[j]>arr[j+1]) {
            swap(arr[j],arr[j+1]);
        }
    }
}
1
2
3
4
5
6
7
8
9
arr=[64,25,12,22,11]
n=len(arr)

for i in range(n):
    for j in range(n-1-i):
        if arr[j]>arr[j+1]:
            arr[j],arr[j+1]=arr[j+1],arr[j]

print(arr)

gif圖示:

圖源自維基百科

2. 選擇排序法 (Selection Sort)

基本上也是兩層迴圈下去跑，找到整個陣列中的最小值，把數值存在變數中，跟前面的換。

時間複雜度 O(n²)

基本架構:

1
2
3
4
5
6
7
8
9
for (int i=0;i<n-1;i++) {
    int mn=i;
    for (int j=i+1;j<n;j++){
        if (arr[j]<arr[mn]){
            mn=j; 
        }
        swap(arr[mn],arr[i]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
arr=[5,4,2,3,1]
n=len(arr)
print(n)
for i in range(n):
    min_idx=i
    for j in range(i+1,n):
        if arr[j]<arr[min_idx]:
            min_idx=j
    arr[i],arr[min_idx]=arr[min_idx],arr[i]
    print(arr)
    
print("===")
print(arr)

gif圖示:

圖源自維基百科

3. 插入排序法 (Insertion Sort)

常用for+while去跑，後面的數值插到前面最適合的位子

時間複雜度 O(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
原始陣列:
( |的前方是排序好的陣列 )
1   2   4   5   6   |   3   8   7
                        ^

3要往前插到最適合的位子
1   2   4   5   6   |   3   8   7
                  ^ (3跟6比，3<6所以繼續往前比)
1   2   4   5   6   |   3   8   7
              ^ (3跟5比，3<5所以繼續往前比)
1   2   4   5   6   |   3   8   7
          ^ (3跟4比，3<4所以繼續往前比)
1   2   4   5   6   |   3   8   7
      ^ (3跟2比，3>2所以插這邊最適合)

按照邏輯用迴圈往下跑...
1   2   3   4   5   6   |   8   7
                       ^ (8跟6比，8>6所以插這邊最適合)
1   2   3   4   5   6   8   |   7
                          ^ (7跟8比，7<8所以繼續往前比)
1   2   3   4   5   6   8   |   7
                      ^ (7跟6比，7>6所以插這邊最適合)

final:
1   2   3   4   5   6   7   8   |
                
1
2
3
4
5
6
7
8
9
for (int i=1;i<n;i++) {
    int key=arr[i];
    int j=i-1;
    while (j>=0&&arr[j]>key) {
        arr[j+1]=arr[j];
        j--;
    }
    arr[j+1]=key;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
arr=[64,25,12,22,11]
n=len(arr)

for i in range(1,n):
    key=arr[i]
    j=i-1
    while j>=0 and arr[j]>key:
        arr[j+1]=arr[j]
        j-=1
    arr[j+1]=key

print(arr)

gif圖示:

圖源自維基百科

4.合併排序法 (Merge Sort)

將陣列每次拆分成兩組同大小的子陣列，直到每組都只有一個元素再進行排序後合併。

時間複雜度: O(n log(n))

拆分再合併 直接看圖示

gif圖示:

圖源自維基百科, emre.me

5.快速排序法 (Quick Sort)

隨機找pivot(基準?) 比pivot小丟左邊 比pivot大丟右邊

時間複雜度: O(n log(n))

★★最常用★★

1
2
3
4
5
6
int n=6;
int a[n]={2,7,1,6,9,5};
sort(a,a+n); 
//排完序: 1,2,5,6,7,9
//函式直接代 意思用看的就懂了
//要注意需含標頭檔 #include<algorithm> 或直接 #include<bits/stdc++.h>

如果是vector也通用

1
2
vector<int> v;
sort(v.begin(),v.end());

sort 自訂排序

排序不是只有由小到大
有時候題目會有大到小或奇數大到小、偶數小到大

遇到這種怎辦?
當然直接sort就好了 :)
看code:

1
2
3
4
5
6
7
vector<int> v;
v.resize(n);

bool cmp(int a, int b){  //自訂排序方式
    return a>b; //代表前面的比後面的大
}
sort(v.begin(),v.end(),cmp); //直接這樣寫就ok

gif圖示:

圖源自維基百科

例題

ZeroJudge a104

ZeroJudge a233

ZeroJudge a915

ZJ a104

selection sort

AC code:

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++){
			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';
		}
	}
}

bubble sort

AC code:

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 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';
		}
	}
}

當然 也不用這麼複雜

quick sort

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(cin >> n){
        vector <int> a(n); 
        for(int &x : a) cin >> x;
        sort(a.begin(), a.end());
        for(int i = 0;i < n;i++){
            cout << a[i] << " \n"[i == n-1];
        }
    }
}

ZJ a233

AC code:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	vector<int> v;
	int n,a;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>v[i];
	}
	sort(v.begin(),v.end());
	for(int i=0;i<n;i++) cout<<v[i]<<" ";
}

ZJ a915

struct

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;
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';
    }
}

no struct

AC code:

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';
    }
}

pair

座標題用pair有時候很方便
first存x軸 second存y軸
AC code:

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 main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int n;
	pair<int,int> p[1005];
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>p[i].first>>p[i].second;
	}
	sort(p,p+n);
	
	for(int i=0;i<n;i++){
		cout<<p[i].first<<" "<<p[i].second<<"\n";
	}
		
}

無營利 僅供分享
資料來源:維基百科

觀念題題庫

https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2022/10/%E8%A7%80%E5%BF%B5%E9%A1%8C_%E9%A1%8C%E5%9E%8B%E7%AF%84%E4%BE%8B.pdf