# 排序 & 初探STL
`第6週社課`
關於排序的部分內容可以參考新竹實驗中學的講義Ch13：
https://hackmd.io/@CLKO/ry9twDVpW?type=view
其他關於STL沒教到的內容可以參考維基百科：
https://zh.wikipedia.org/zh-tw/%E6%A0%87%E5%87%86%E6%A8%A1%E6%9D%BF%E5%BA%93
<!-- 顏色字體： -->
<!-- <span style="color:#0000FF"> str <span> -->
## 目錄
* <a href="##STL介紹" style="color: black; ">STL介紹</a>
* <a href="##vector" style="color: black; ">vector</a>
* <a href="##pair" style="color: black; ">pair</a>
* <a href="##Counting-Sort(補充)" style="color: black; ">Counting Sort</a>
* <a href="##sort函數" style="color: black; ">sort函數</a>
* <a href="##多欄位排序" style="color: black; ">多欄位排序</a>
* <a href="##stable_sort" style="color: black; ">stable_sort</a>
## STL介紹
**STL**(標準樣板函式庫 Standard Template Library)，是一個C++軟體庫，裡面包含了常用到的基本資料結構與演算法(函數)，正確的使用可以有效**簡化程式設計**。
### 資料結構？
資料結構就是儲存資料的容器，不同的資料結構會以不同的方法儲存這些資料，
只要使用正確的資料結構就可以提升程式的效率(**壓低複雜度**)
### 內容
STL主要包含以下內容：(引用自維基百科)
* 容器(container)：包含、放置資料的地方。
* 指位器(iterator)：用來指定操作所涉及到的記憶體位置(範圍)。
* 演算法(algorithm)：要執行的操作(Ex:排序演算法)。
* (其他不在此處介紹)
其實這些名詞對於競程都不是很重要，只要會用就好了。
以下的內容都只會教怎麼用，沒有講原理。
## vector
### 功能
可以改變大小的陣列，它和傳統陣列最大的差異就是：使用時可以不用預先知道需要多少記憶體，
直接動態分配。
因為它最常用，所以放在第一個講
### 宣告
```
vector<type> v(size, init);
```
type : 內容物種類
v : vector名稱
size : vector初始大小，可以省略(預設為0)
init : 每一項的初始值，可以省略(預設為0)
不可以省略size但保留init，因為不知道初始大小就不可能填入初始值
Ex：
```cpp
vector<int> v1; // 空陣列
vector<int> v2(5); // 5個0
vector<int> v3(10,1); // 10個1
```
二維陣列就是把int改成vector<int>，依此類推。
```cpp
vector<vector<int>> v1;
vector<vector<int>> v2(3, vector<int>(2,0));
// {{0,0}, {0,0}, {0,0}}
```
vector結合傳統陣列：
```cpp
vector<int> v[1000];
```
這是一個二維陣列，由1000個vector組成
### 使用
```cpp
// 取值，如同一般陣列(i必須小於v.size())
v[i]
// 從後方加入元素
v.push_back(x);
// 從後方刪除元素
v.pop_back();
// 手動調整大小
v.resize(sz);
// 取得大小
v.size()
// 清除全部
v.clear();
// 回傳是否為空
v.empty()
```
### 迴圈遍歷
#### 先備知識
* v.begin() 指向v的第一項的指標
* v.end() 指向v的最後一項的下一個位置的指標
* v.rbegin() 指向v的最後一項的反向指標
* v.rend() 指向v的第一項的前一個位置的反向指標
#### 正向(指標)
STL
```cpp
vector<int> v(5,1);
for (auto m = v.begin(); m != v.end(); m++) {
cout << *m << " ";
}
```
或是
```cpp
for_each(v.begin(), v.end(), func);
```
傳統陣列
```cpp
for (int i = 0; i < n; ++i) {
//do something with *(a + i)
}
```
#### 反向(指標)
STL
```cpp
vector<int> v(5,1);
for (auto m = v.rbegin(); m != v.rend(); m++) {
cout << *m << " ";
}
```
auto表示讓編譯器來判斷變數的型態，因為型態的名稱太長了
傳統陣列
```cpp
for (int i = n - 1; i >= 0; --i) {
//do something with *(a + i)
}
```
#### auto
```cpp
vector<int> v(5,1);
for (auto &i : v) {
cout << i << " ";
}
```
## pair
### 功能
把兩個不同的變數型別綁在一起，廣泛使用在不同實作中
### 宣告
```
pair<type1,type2> p;
```
如果今天要把變數塞進去的話，有兩種方法
第一種是簡潔的
```cpp
pair<int, char> p = {10, 'c'};
```
第二種是在第一種被編譯器判定為語意太模糊情況下使用
```cpp
pair<int, char> p = make_pair(10, 'c');
```
### 取值
```cpp
p.first
p.second
```
### 省略
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
int main{
pair<int, int> p;
cin >> p.ff >> p.ss;
}
```
## Counting Sort(補充)
### 功能
計數排序，一種$O(n)$的排序法，只有在題目的數字範圍不大時用了才比較好
例如今天想排序
```
1 4 2 7 10 8 7 7 1 9 1 1 10
```
那麼
紀錄每個數字出現次數(假設數字最大到12)
```
1 2 3 4 5 6 7 8 9 10 11 12
4 1 0 1 0 0 3 1 1 2 0 0
```
再輸出到一個陣列就結束了，或whatever你要怎麼做
```
1 1 1 1 2 4 7 7 7 8 9 10 10
```
### 範例程式碼
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000;
vector<int> chart(MAX_N);
int main() {
int i, n, num;
cin >> n;
for (i = 0; i < n; ++i) {
cin >> num;
++chart[num];
}
for (i = 0; i < MAX_N; ++i) {
while (chart[i]--) {
cout << i << ' ';
}
}
}
```
## sort函數
### 語法
```
sort(iterator_begin, iterator_end, compare_function)
compare_function default = less<type>
```
### 時間
c++ 內建 $\Theta(n \log n)$ 的排序函數
### 實際
不用你手刻merge sort
```cpp
vector<int> a = {1, 2, 4, 1, 4, 2, 3, 1};
sort(a.begin(), a.end());
```
## 排序傳統陣列
```cpp
sort(a+0, a+n);
```
排序$a_0$到$a_{n-1}$
## 多欄位排序
less<int>()，greater<long long>()不夠用了嗎？
沒關係，自訂義compare函數搞定一切
第一種作法：在定義該資料型別時直接宣告入其中
```cpp
struct point {
int x, y;
bool operator< (const point other) const {
if (x == other.x) return y < other.y;
return x < other.x;
}
};
vector<point> v;
for(int i = 0; i < n; i++){
cin >> v[i].x >> v[i].y;
}
sort(v.begin(), v.end());
```
第二種作法：直接寫好cmp函數放到sort裡面用
```cpp
struct point {
int x, y, z;
};
bool cmp(const point A, const point B) {
if (A.z == B.z) {
if (A.y == B.y) return A.x < B.x;
return A.y < B.y;
}
return A.z < B.z;
}
vector<point> v;
for(int i = 0; i < n; i++){
cin >> v[i].x >> v[i].y >> v[i].z;
}
sort(v.begin(), v.end());
```
如果你想要first正著排，second倒著排：
```cpp
#include <bits/stdc++.h>
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
bool cmp(pii a, pii b){
if(a.ff == b.ff){
return a.ss > b.ss;
}
return a.ff < b.ff;
}
int main(){
int n;
cin >> n;
vector<pii> v(n);
for(int i = 0; i < n; i++){
cin >> v[i].ff >> v[i].ss;
}
sort(v.begin(), v.end(), cmp); // cmp後面不用加括號
for(int i = 0; i < n; i++){
cout << v[i].ff << " " << v[i].ss << "\n";
}
return 0;
}
```
輸入：
```
7
1 1
1 2
1 3
1 4
1 5
2 1
2 2
```
輸出：
```
1 5
1 4
1 3
1 2
1 1
2 2
2 1
```
### 範例：CSES Movie Festival
現場實作
## stable_sort
### 語法
```
stable_sort(iterator_begin, iterator_end, compare_function)
compare_function default = less<type>
```
### 時間
支持"保序"，就是說相對位置不會變
對於無須交換的兩項，它保證排序後這兩項不會被交換
Ex：對pair排序，但只排序第一項。
那麼在排序{0,1}和{0,2}時，stable_sort保證這兩項會維持其原本的順序，
但一般的sort函數不保證，也就是說這兩項有可能在排序的過程中被交換
c++ 內建 ，$O(n \log n)$，$\Theta(n\log n)$ 的排序函數
對於給定額外空間$O(n)$的情況下有$O(n\log n)$
原地排序變成$O(n\log^2n)$
（$O$：最壞時間複雜度，$\Theta$：平均時間複雜度）
### 實際
不用你手刻merge sort
```cpp
vector<int> a = {1, 2, 4, 1, 4, 2, 3, 1};
stable_sort(a.begin(), a.end());
```
Sign in with Wallet
Connect another wallet