# 搜尋與排序
Wiwi Ho
###### tags: `CRC`
---
https://hackmd.io/@wiwiho/crc1082algo
https://tg.pe/xgaG
![](https://i.imgur.com/KqGWkCw.png)
---
# 比大小
---
## 怎麼比大小
----
## 全序關係
----
記作 $\leq$
就是常見的比較符號
----
但意義不一定是平常說的小於等於
這裡的 $\leq$ 就純粹是一種符號
沒有固定的意義
----
某集合 $X$ 滿足全序關係的條件:
- $\forall a,b \in X, a \leq b \land b \leq a \Rightarrow a = b$
- $\forall a,b,c \in X, a \leq b \land b \leq c \Rightarrow a \leq c$
- $\forall a,b \in X, a \leq b \lor b \leq a$
----
也就是說,$X$ 內的每一對元素要可以互相比較
----
## 非嚴格全序
----
記作 $<$
就是 $\leq$ 少 $=$
----
性質:
- $\forall a,b,c \in X, a < b \land b < c \Rightarrow a < c$
- $\forall a,b \in X, a < b \lor b < a \lor a = b$
----
## 偏序關係
----
也記為 $\leq$
----
性質:
- $\forall x \in X, x \leq x$
- $\forall a,b \in X, a \leq b \land b \leq a \Rightarrow a = b$
- $\forall a,b,c \in X, a\leq b \land b \leq c \Rightarrow a \leq c$
----
和全序的差別是
偏序關係不需要每一對元素都能互相比較
----
## 單調性
----
函數 $f: X \to Y$
----
非嚴格遞增
$\forall x_1,x_2 \in X \land x_1 \leq x_2, f(x_1) \leq f(x_2)$
----
嚴格遞增
$\forall x_1,x_2 \in X \land x_1 \leq x_2, f(x_1) < f(x_2)$
----
非嚴格遞減
$\forall x_1,x_2 \in X \land x_1 \leq x_2, f(x_1) \geq f(x_2)$
----
嚴格遞減
$\forall x_1,x_2 \in X \land x_1 \leq x_2, f(x_1) > f(x_2)$
---
## Comparator
----
用來定義比較方式的 function
放在跟比較有關的 function 的參數
和 container 的 template
----
```cpp=
vector<int> a;
sort(a.begin(), a.end()); //把 a 裡的東西由小到大排序
sort(a.begin(), a.end(), less<>()); //把 a 裡的東西由小到大排序
sort(a.begin(), a.end(), greater<>()); //把 a 裡的東西由大到小排序
set<int> s1; //s1 裡的東西會由小到大排序
set<int, less<>> s2; //s2 裡的東西會由小到大排序
set<int, greater<>> s3; //s3 裡的東西會由大到小排序
```
----
## less<>、greater<>
STL 提供的 comparator
表示使用 $<$ 和 $>$ 運算子
----
## 自己實作
----
struct 版
```cpp=
struct Comp{
bool operator()(T a, T b){
return /*...*/;
}
};
//...
vector<T> a;
sort(a.begin(), a.end(), Comp());
set<T, Comp> s;
```
----
function 版
```cpp=
bool comp(T a, T b){
return /*...*/;
}
//...
vector<T> a;
sort(a.begin(), a.end(), comp);
```
----
lambda 版
```cpp
vector<T> a;
sort(a.begin(), a.end(), [](T a, T b){return /*...*/;});
```
---
# 搜尋
---
## 二分搜尋法
----
猜數字?
----
```cpp
int l = /*初始下界*/, r = /*初始上界*/;
while(l < r){
int m = (l + r) / 2;
if(check(m)) //變更邊界
else //變更邊界
}
```
----
變更邊界
- $l=m$
- $r=m$
- $l=m+1$
- $r=m-1$
----
怎麼選 $m$
如果有狀況會把 $l$ 變更成 $m$
當 $l+1=r$ 時,$m=\lfloor\frac{2l+1}{2}\rfloor=l$
範圍會卡住
改成 $m=\lfloor\frac{l+r+1}{2}\rfloor$
----
## 範例
----
給遞增數列 $a_1 \leq a_2 \leq a_3 \leq ... \leq a_n$
和數字 $x$
求最小的 $i$ 滿足 $a_i \geq x$
保證有解
----
```cpp
vector<int> a(n);
int x;
//...
int l = 0, r = n - 1;
while(l < r){
int m = (l + r) / 2;
if(a[m] >= x) r = m;
else l = m + 1;
}
```
----
## 時間複雜度
----
每次範圍大小變為本來的約一半
$\Rightarrow$ 時間複雜度 $O(\log_2 n)=O(\log n)$
----
## 對答案二分搜
----
[ZeroJudge c575](https://zerojudge.tw/ShowProblem?problemid=c575)
有 $N$ 個服務點
你最多可以放 $K$ 個基地台
並決定一個盡量小的半徑 $R$
使每一個服務點都有一個距離它至多 $R$ 的基地台
求最小的 $2R$
----
如果 $R=x$ 時可以找到放基地台的方法
那 $R>x$ 時也可以
$\Rightarrow$ 二分搜最小的可以找到怎麼放基地台的 $R$
----
怎麼找?
盡量把基地台往後放
----
## STL 裡的二分搜
----
lower_bound(l, r, n, comp)
回傳 $[l,r)$ 中第一個不小於 $n$(由 comp 定義)的元素位置
----
upper_bound(l, r, n, comp)
回傳 $[l,r)$ 中第一個大於 $n$(由 comp 定義小於)的元素位置
---
## 三分搜尋法
----
二分搜:把範圍分兩段
三分搜:把範圍分三段
----
分隔點
![](https://i.imgur.com/f3a8MGk.png)
----
## 範例
----
有一開口向上的二次函數 $f(x)$
求頂點
----
```cpp=
double l = -1e9, r = 1e9;
while(r - l > 1e-4){
double m1 = (2 * l + r) / 3;
double m2 = (l + 2 * r) / 3;
if(f(m1) < f(m2)) r = m2;
else l = m1;
}
cout << l << " " << r << "\n";
```
---
# 排序
---
## STL 裡的排序
```cpp
sort(l, r, comp)
```
---
## 氣泡排序
----
分成已排序部分和未排序部分
----
一開始整個序列都是未排序的
----
找到未排序部分裡最大的元素
移到未排序部分的尾端
----
實作方式
第一個元素和第二個元素比較
第一個元素比較大就交換
第二個元素和第三個比較
如果第二個比較大就交換……
未排序部分的倒數第二個元素和倒數第一個元素比較
倒數第二個比較大就交換
----
然後最後一個元素會加入已排序部分
未排序部分的大小少 1
接著重複一樣的動作
直到排序完為止
----
```cpp=
vector<int> a(n);
//...
for(int i = 0; i < n - 1; i++){
for(int j = 0; j < n - i - 1; j++){
if(a[j] > a[j + 1]) swap(a[j], a[j + 1]);
}
}
```
----
複雜度
$O(n^2)$
---
## 插入排序
----
同樣分成已排序部分和未排序部分
但通常未排序部分會放前面
----
在未排序部分裡找隨便一個數字
再找到它應該放在已排序部分的哪裡
然後塞進去
未排序部分大小會少 1
然後重複一樣的動作
----
實作方式
暴力
----
```cpp=
vector<int> a(n);
//...
for(int i = 1; i < n; i++){
int pos = i;
for(int j = i + 1; j < n; j++){
if(a[j] < a[pos]) pos = j;
}
int p;
for(p = 0; p < i; p++){
if(a[p] > a[pos]) break;
}
int t = a[pos];
for(int j = pos; j > p; j--) a[j] = a[j - 1];
a[p] = t;
}
```
----
時間複雜度
$O(n^2)$
---
## 合併排序
----
把序列切兩半
分別排序過後再合併
=某種遞迴
----
$\text{mergesort}(l,r)$:
將 $[l,r]$ 範圍排序
$m=\frac{l+r}{2}$
呼叫 $\text{mergesort}(l,m)$ 和 $\text{mergesort}(m + 1, r)$
再把兩邊合併
----
```cpp=
void mergesort(vector<int>& a, int l, int r){
if(l == r) return;
int m = (l + r) / 2;
mergesort(a, l, m);
mergesort(a, m + 1, r);
vector<int> b;
int lp = l, rp = m + 1;
while(lp <= m && rp <= r){
if(a[lp] <= a[rp]) b.eb(a[lp]), lp++;
else b.eb(a[rp]), rp++;
}
while(lp <= m) b.eb(a[lp]), lp++;
while(rp <= r) b.eb(a[rp]), rp++;
for(int i = 0; i < r - l + 1; i++) a[l + i] = b[i];
}
//...
vector<int> a(n);
//...
mergesort(a, 0, n - 1);
```
----
時間複雜度
----
遞迴到相同深度的
範圍不會重疊
且聯集是整個序列
----
遞迴深度
每遞迴一層
範圍大小會少約一半
$O(\log n)$
----
![](https://i.imgur.com/8io8MHr.png)
----
$O(n \log n)$
---
## 快速排序
----
和合併排序相似
把範圍分兩邊分別排序
但不是直接切中間
----
選一個元素當 pivot
比它小的元素都放到它左邊
比它大的元素都放到它右邊
兩側遞迴排序
----
```cpp=
void quicksort(vector<int>& a, int l, int r){
if(l >= r) return;
int pv = /*...*/;
swap(a[pv], a[r]);
int lp = l, rp = r - 1;
while(lp < rp){
while(lp < rp && a[lp] <= a[r]) lp++;
while(lp < rp && a[rp] > a[r]) rp--;
swap(a[lp], a[rp]);
}
if(a[rp] <= a[r]) rp = r;
swap(a[rp], a[r]);
quicksort(a, l, rp - 1);
quicksort(a, rp + 1, r);
}
//...
vector<int> a(n);
//...
quicksort(a, 0, n - 1);
```
----
複雜度
----
遞迴到一樣深度的
範圍不重疊
聯集也是整個序列
$\Rightarrow$ 複雜度是 遞迴深度 $\times O(n)$
----
遞迴深度?
和遞迴一層,範圍如何改變有關
----
如果每次範圍少 1
深度就是 $O(n)$
----
如何選 pivot?
選定點:很好構出每次範圍少 1 的 case
Random!
----
有 $\frac{1}{2}$ 機率選到中間 50% 的元素
i.e. 比它小至少 25%、比它大至少 25%
範圍最多變 $\frac{3}{4}$
----
要選到最多
$\log_{\frac{4}{3}} n=\frac{log_2 n}{log_2 \frac{4}{3}} \approx 2.409 \log_2 n$
次滿足條件的 pivot
----
選到的機率是 $\frac{1}{2}$
$\Rightarrow$ 約 $2 \times 2.409 \log_2 n$ 次就可選到 $2.409 \log_2 n$ 次
遞迴深度 $=O(2 \times 2.409 \log_2 n)=O(\log n)$
複雜度 $O(n \log n)$
----
如果沒有這樣的元素能當 pivot?
----
如果幾乎所有元素都一樣
那和 pivot 一樣的元素一定會被丟到同一邊
$\Rightarrow$ 變 $O(n^2)$
----
解決方法
換成 pair,讓每個元素長不一樣
---
## 基數排序
----
非比較排序
----
從數字最低位開始看
拿十個桶子
最低位是幾就放第幾個桶子
----
從編號小的桶子開始依序拿出
放回序列
序列會按最低位排序
----
看次低位
也拿十個桶子
這一位是幾就放第幾個桶子
序列會按次低位排序,相同的按最低位
----
一直往高位看
----
```cpp=
vector<int> a;
//...
vector<pair<int, int>> t(a.size());
for(int i = 0; i < a.size(); i++) t[i] = make_pair(a[i], a[i]);
while(max_element(t.begin(), t.end())->F > 0){
vector<vector<pair<int, int>>> b(10);
for(auto i : t) b[i.F % 10].emplace_back(i);
t.clear();
for(int i = 0; i < 10; i++){
for(auto j : b[i]){
t.emplace_back(make_pair(j.first / 10, j.second));
}
}
}
for(int i = 0; i < a.size(); i++) a[i] = t[i].S;
```
----
複雜度
----
令 $x=2^{63}-1=$ long long 最大值
會看 $log_{10} x$ 位,$O(\log_{10} x)$
看每一位時
掃 $10+1$ 次數列,算作 $O(10n)$
總複雜度 $O(10n \log_{10} x)=O(n)$?
----
常數
$10 \log_{10} x \approx 190$
----
用別的底?
$O(bn \log_b x)$
常數:$b \log_b x$
----
不管怎樣都很大
---
## 例題
----
[ZeroJudge c471](https://zerojudge.tw/ShowProblem?problemid=c471)
有 $N$ 個物品
你必須把它們疊起來
成本是 $\sum_{i=1}^N f(i) \times \sum_{j=\text{所有在它上面的東西} w(j)}$
最小化成本
----
只有兩個物品時
如果 1 在 2 上方
成本:$w(1) \times f(2)$
如果 2 在 1 上方
成本:$w(2) \times f(1)$
----
如果 $w(1) \times f(2) < w(2) \times f(1)$
1 就要在 2 上面
移項
$\frac{w(1)}{f(1)} < \frac{w(2)}{f(2)}$
某種全序關係?
----
在一種堆疊順序中
相鄰的兩個物品交換
和其他物品相對位置不變
所以對成本的改變只和它們有關
----
如果 $i$ 在上 $j$ 在下
若 $\frac{w(i)}{f(i)} > \frac{w(j)}{f(j)}$
把它們交換後成本會變小
----
按 $w(i) \times f(j) < w(j) \times f(i)$ 排序
----
```cpp
#include <bits/stdc++.h>
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long ll;
using namespace std;
vector<ll> f, w;
bool comp(int i, int j){
return w[i] * f[j] < w[j] * f[i];
}
int main(){
StarBurstStream
int n;
cin >> n;
f.resize(n);
w.resize(n);
for(int i = 0; i < n; i++) cin >> w[i];
for(int i = 0; i < n; i++) cin >> f[i];
vector<int> a(n);
for(int i = 0; i < n; i++) a[i] = i;
sort(a.begin(), a.end(), comp);
ll ans = 0;
ll sum = 0;
for(int i = 0; i < n; i++){
ans += sum * f[a[i]];
sum += w[a[i]];
}
cout << ans << "\n";
return 0;
}
```
{"metaMigratedAt":"2023-06-15T07:51:33.960Z","metaMigratedFrom":"Content","title":"搜尋與排序","breaks":"false","description":"Wiwi Ho","contributors":"[{\"id\":\"02353542-5acb-4a66-abd0-128b1af24abb\",\"add\":9010,\"del\":24}]"}