排序
常見排序法
排序前必要條件:
所有值必須丟到一個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]);
}
}
}
|
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]);
}
}
|
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;
}
|
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);
|
如果是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);
|
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";
}
}
|
無營利 僅供分享
資料來源:維基百科
觀念題題庫
如果有不會的 午休時間我在資訊教室!
版權聲明: 此文章版權歸che哲所有，可轉載，禁止營利
