# 基本的排序法
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] <<' ';
}
```
---
# 謝謝大家
{"description":"type : slide","title":"基本的排序演算法","contributors":"[{\"id\":\"b49547c8-0e7f-46d0-99b2-8a45dfee8e90\",\"add\":4439,\"del\":303}]"}