排序sort

資料來源：https://openhome.cc/zh-tw/algorithm/sort/abc/

選擇排序

如果排序是由小而大，從後端未排序部份選擇一個最小值，並放入前端已排序部份的最後一個。例如排序前 70、80、31、37、10、1、48、60、33、85。

[1] 80 31 37 10 70 48 60 33 85（選出最小值 1，1與70交換）

[1 10] 31 37 80 70 48 60 33 85（選出最小值 10，10與80交換）

[1 10 31] 37 80 70 48 60 33 85（選出最小值 31）

[1 10 31 33] 80 70 48 60 37 85（選出最小值 33，33與37交換）

[1 10 31 33 37] 70 48 60 80 85（選出最小值 37，37與80交換）

[1 10 31 33 37 48] 70 60 80 85（選出最小值 48，48與70交換）

[1 10 31 33 37 48 60] 70 80 85（選出最小值 60，60與70交換）

[1 10 31 33 37 48 60 70] 80 85（選出最小值 70）

[1 10 31 33 37 48 60 70 80] 85（選出最小值 80）

[1 10 31 33 37 48 60 70 80 85]（選出最小值 85）

插入排序

每次從後端未排序部份取得最前端的值，然後插入前端已排序部份的適當位置。例如排序前 92、77、67、8、6、84、55、85、43、67。

[77 92] 67 8 6 84 55 85 43 67（將 77 插入 92 前）

[67 77 92] 8 6 84 55 85 43 67（將 67 插入 77 前）

[8 67 77 92] 6 84 55 85 43 67（將 8 插入 67 前）

[6 8 67 77 92] 84 55 85 43 67（將 6 插入 8 前）

[6 8 67 77 84 92] 55 85 43 67（將 84 插入 92 前）

[6 8 55 67 77 84 92] 85 43 67（將 55 插入 67 前）

[6 8 55 67 77 84 85 92] 43 67（將 85 插入 92 前）

[6 8 43 55 67 77 84 85 92] 67（將 43 插入 55 前）

[6 8 43 55 67 67 77 84 85 92]（將 67 插入 77 前）

氣泡排序

排序時若是從小到大，以比較相鄰元素的方式，將較大元素交換至右端，較大的元素會不斷往右移動，像是氣泡一樣，直到適當位置為止。例如排序前 95、27、90、49、80、58、6、9、18、50。

27 90 49 80 58 6 9 18 50 [95]（95 浮出）

27 49 80 58 6 9 18 50 [90 95]（90 浮出）

27 49 58 6 9 18 50 [80 90 95]（80 浮出）

27 49 6 9 18 50 [58 80 90 95]（58 浮出）

27 6 9 18 49 [50 58 80 90 95]（50 浮出）

6 9 18 27 [49 50 58 80 90 95]（49 浮出）

6 9 18 [27 49 50 58 80 90 95]（27 浮出）

6 9 [18 27 49 50 58 80 90 95]（18 浮出）

6 [9 18 27 49 50 58 80 90 95]（9 浮出）

[6 9 18 27 49 50 58 80 90 95]（6 浮出）

氣泡排序法可以利用旗標方式稍微減少比較時間，當尋訪完未排序部份都沒有發生任何交換動作，表示排序已經完成，不再進行後續的比較與交換動作。

merge sot 合併演算法

時間複雜度 O(log n)
影片來源：https://www.youtube.com/watch?v=C9Xes8wH6Co

自定義順序

一、
先宣告一個陣列int v[n]={6,4,3,5,8}，共n=5項。
二、
把a想成左邊（前一項），b想成右邊（後一項），回傳是最後結果(左邊>右邊)

Danger | 口訣

cmp(a, b) 回傳 true，代表 a 應該排在 b 前面(左邊)。

#include <bits/stdc++.h>
using namespace std;
bool cmp(int a,int b){
    return a>b;
}

int main(){
    int v[10]={6,4,3,5,8};
    sort(v,v+5,cmp);
    for(int i=0;i<5;i++){
        cout<<v[i]<<" ";
    }
}

8 6 5 4 3

Danger | 要注意不能讓cmp變數x、y資料型態為auto，會錯誤

---

也可以多個欄位，如下

#include <bits/stdc++.h>
using namespace std;
struct st{
    int x;
    int y;
}v[10];
bool cmp(st a,st b){
    return a.y>b.y;
}
int main(){
    istringstream cin("6 4 3 5 8 7");

    for(int i=0;i<3;i++){
        cin>>v[i].x>>v[i].y;
    }
    sort(v,v+3,cmp);
    for(int i=0;i<3;i++){
        cout<<v[i].x<<" "<<v[i].y<<"\n";
    }
}

8 7
3 5
6 4

以上是按照v[]中每個st元素的y為依據，一樣不能用auto為型態