---
# System prepended metadata

title: 基本的排序演算法
tags: [進階組]

---

---
type : slide
---

# 基本的排序法
by:hush

---

## 排序？

----

排序就是把物品照順序排好

排序演算法是非常重要且基本的工具，很多題目都需要使用到它，也很適合拿來練習實作

---

## 各種排序演算法

----

### 氣泡排序法(Bubble sort)

----

- 方法：
    先從頭跑到尾，每次比較相鄰的兩個元素，若前面的較後面的大則交換，跑完最大的元素會在最後，接著從頭跑到倒數第二個，一樣順序錯就交換，如此最後兩個元素就排好了，... ...直到全部排好

----

{%youtube 9I2oOAr2okY%}

----

code:
```cpp=
#include<bits/stdc++.h>
#define int long long 
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);

using namespace std;

void Bubble_sort(int n,int a[])
{
    for (int end=n-1;end>=1;end--) //終點到1就好
        for (int i=0;i<end;i++)
            if (a[i]>a[i+1]) //逆序
            {
                swap(a[i],a[i+1]); //交換   
            }
}

signed main()
{
    //colinorz;
    int n,a[100005]; cin >> n;
    for (int i=0;i<n;i++) cin >> a[i];
    
    Bubble_sort(n,a);
    
    for (int i=0;i<n;i++) cout << a[i] <<' ';
}
```

----

### 選擇排序法(Selection sort)

----

- 方法：
    從頭跑到尾，用一個變數維護最大值，然後把最大值跟最後一個元素交換，接著從頭跑到倒數第二，找出其中的最大值，跟倒數第二個元素交換，... ...
    

----

{%youtube 92BfuxHn2XE %}

----

code:
```cpp=7
void Selection_sort(int n,int a[])
{
    for (int end=n-1;end>=1;end--) //終點到1就好
    {
        int max=-1e18,tmp=end;
        for (int i=0;i<=end;i++) //要跑到最後
            if (a[i]>max) //找到更大值
            {
                tmp=i; //更新最大值位置
                max=a[i]; //更新最大值
            }
        swap(a[end],a[tmp]);
    }
}
```

----

### 插入排序法(Insertion sort)

----

- 方法：
    維護一個照順序的陣列，每次從原先陣列拿一個元素，從新陣列最後往前比對，若遇到的元素較大，則繼續往前比對，否則將元素停在該位置，直到所有元素都拿完


----

{%youtube mTNC0ERo-ZI%}

----

如同影片，一般實作上會將陣列前半部做為已排序陣列，後半部為未排序陣列，就不需要開兩個了

----

code:
```cpp=7
void Insertion_sort(int n,int a[])
{
    for (int begin=1;begin<n;begin++) //從1開始就好
    {
        for (int i=begin;i>=0 && a[i]<a[i-1];i--) //直到遇到更小的才停止
        {
            swap(a[i],a[i-1]);
        }
    }
}
```

----

### 總結：
這些排序法的共通點是都用到雙層迴圈，外層決定移動哪個元素，內層決定移動到哪，兩層的時間複雜度都是$O(n)$，所以總時間複雜度為$O(n^2)$

---

## STL的排序工具

----

雖然有手刻的技能很重要，但因為題目太常用到排序了，所以就有大佬幫我們寫好方便又快速的排序函式(理論上是最快的)

----

### std::sort

----


{%youtube 67ta5WTjjUo %}

----

首先要
```=
#include <algorithm>
```

----

使用的語法(a是陣列名稱，n是長度)
```cpp=8
    sort( a, a+n );
```

----

如果是排序vector
```cpp=8
    sort(v.begin(),v.begin()+n);
```

講義有更詳細的語法範例

----

例如：
```cpp=
#include<iostream>
#include<algorithm>

using namespace std;

signed main()
{
    //colinorz;
    int n,arr[100005]; cin >> n;
    for (int i=0;i<n;i++) cin >> arr[i];
    
    sort(arr,arr+n);
    
    for (int i=0;i<n;i++) cout << arr[i] <<' ';
}
```

----

預設是升冪排序(小到大)，若要降冪排序可用

```cpp=8
    sort( a, a+n, greater<int>() );
```

----

或是使用自定義的比較函式

```cpp=
#include<iostream>
#include<algorithm>
using namespace std;

bool cmp(int a,int b)
{
    return a>b; //回傳true不交換
}

signed main()
{
    //colinorz;
    int n,arr[100005]; cin >> n;
    for (int i=0;i<n;i++) cin >> arr[i];
    
    sort(arr,arr+n,cmp);
    
    for (int i=0;i<n;i++) cout << arr[i] <<' ';
}
```

----

如果想要穩定排序就用
```cpp=8
    stable_sort( a, a+n );
```
sort => stable_sort，其他全部一樣

---

## 練習題

----

- 前面三種排序法自己寫一遍，**不要用背的**
- [CSDC64](https://csdc.tw/problem/64/)
- [CSDC384](https://csdc.tw/problem/384/)
- [CSDC231](https://csdc.tw/problem/231/) (進階題)

----

- CDSC64題解：
    選一個你喜歡的演算法手刻


----


AC code:
```cpp=
#include<bits/stdc++.h>
#define int long long 
#define colinorz cin.tie(0);cout.tie(0);ios:sync_with_stdio(0);

using namespace std;

int a[1005];

signed main()
{
    //colinorz;
    int n; cin >> n;
    for (int i=0;i<n;i++) cin >> a[i];
    
    for (int i=1;i<n;i++)
        for (int j=i;j>=0 && a[j]<a[j-1];j--)
            swap(a[j],a[j-1]);
    
    for (int i=0;i<n;i++) cout << a[i] <<' ';
}
```

----

- CSDC231題解：
    如果遇到怪怪條件的排序，就可以使用自定義排序！


----

AC code:
```cpp=
#include<bits/stdc++.h>
#define int long long 
#define colinorz cin.tie(0);cout.tie(0);ios::sync_woith_stdio(0);

using namespace std;

bool cmp(int a,int b)
{
    if (a%3!=b%3)    
        return a%3<b%3;
    return a<b;
}

signed main()
{
    //colinorz;
    int n,arr[1005]; cin >> n;
    for (int i=0;i<n;i++) cin >> arr[i];
    
    sort(arr,arr+n,cmp);
    
    for (int i=0;i<n;i++) cout << arr[i] <<' ';
}
```

---

# 謝謝大家