---
tags: 進階班
---
# 排序和搜尋法
---
## Binary Search (二分搜尋法)
試玩一次範例 `code` 應該就懂了 :poop:
`int` 範圍的二分搜如下(左閉右開):
1. 先設 `l, r`，代表猜數字的範圍
2. 猜的數字比答案大，`r = guess`
3. 猜的數字比答案小，`l = guess + 1`
(你必須回答電腦，電腦猜得太小輸入 1，太大輸入 -1，0 代表正確)
`Time Complexity` : $O(lgN)$
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
#define LL long long
#define f first
#define s second
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int ans;
long long l = 0, r = 4294967296LL;
bool flag = false;
for (int x = 0; x < 33; x++) {
long long m = (l + r) >> 1;
cout << m << '\n';
cin >> ans;
if (ans == 0){flag = true; break;}
else if (ans == 1) l = m + 1;
else if (ans == -1) r = m;
}
if(!flag) break;
}
return 0;
}
```
:::
好用函數介紹：
`lower_bound(v.begin(), v.end(), n)` 找出 `vector` 中，第一個大於等於 `n` 的數字。
`upper_bound(v.begin(), v.end(), n)` 找出 `vector` 中，第一個大於 `n` 的數字。
## Merge Sort (合併排序法)
假設今天要處理的數列是
|5|2|8|6|3|7|1|4|
|-|-|-|-|-|-|-|-|
接下來進行 split (分割) 的動作:
```graphviz
digraph main{
node[color="black" fontcolor="black" fontname="Arial"]
edge[color="black" fontcolor="black"]
fontname=""
{"5, 2, 8, 6, 3, 7, 1, 4"}->{"5, 2, 8, 6","3, 7, 1, 4"}
{"5, 2, 8, 6"}->{"5, 2","8, 6"}
{"3, 7, 1, 4"}->{"3, 7","1, 4"}
{"5, 2"}->{5,2}{"8, 6"}->{8,6}{"3, 7"}->{3,7}{"1, 4"}->{1,4}
}
```
這邊沒什麼好說的，就用遞迴把數列二分成兩組，直到每組分到剩 $1$ 個數字
接下來，開始 merge (合併) ~
先上完整 merge 動作：
```graphviz
digraph main{
node[color="black" fontcolor="black" fontname="Arial"]
edge[color="black" fontcolor="black"]
{5,2}->{"2, 5"}{8,6}->{"6, 8"}{3,7}->{"3, 7"}{1,4}->{"1, 4"}
{"2, 5, 6, 8","1, 3, 4, 7"}->{"1, 2, 3, 4, 5, 6, 7, 8"}
{"2, 5","6, 8"}->{"2, 5, 6, 8"}
{"3, 7","1, 4"}->{"1, 3, 4, 7"}
}
```
可以發現，每合併一層，都要經過排序 (其實就是優化後的 `Selection Sort` )
`Time Complexity` : $O(NlgN)$
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define LL long long
void merge_sort(vector<int>& v) {
if (v.size() != 1) {
//start to split
size_t mid = int(v.size() / 2);
vector<int> left(v.begin(), v.begin() + mid);
vector<int> right(v.begin() + mid, v.end());
merge_sort(left), merge_sort(right);
//start to merge
size_t l = 0, r = 0, x = 0;
while (l != left.size() && r != right.size()) {
if (left[l] <= right[r]) v[x] = left[l], l++;
else v[x] = right[r], r++;
x++;
}
while (l != left.size()) v[x] = left[l], l++, x++;
while (r != right.size()) v[x] = right[r], r++, x++;
}
else return;
}
int main() {
cin.tie(nullptr); ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<int> v(n);
for (auto& i : v) cin >> i;
merge_sort(v);
for (auto& i : v) cout << i << ' ';
return 0;
}
```
:::
## Quick Sort (快速排序法)
和 `Merge sort` 有點像，
只是把數列二分的標準是：
隨便找數列中的一個數字，比該數小就擺左邊，比該數大就擺右邊，
當 `left.size()` 和 `right.size()` $\leq 1$ 時，就排序結束了。
放個例子 (挑的基準數字都是當前數列第一項)
處理數列是：
|5|2|8|6|3|7|1|4|
|-|-|-|-|-|-|-|-|
```graphviz
digraph main{
node[color="black" fontcolor="black" fontname="Arial"]
edge[color="black" fontcolor="black"]
fontname=""
{"5, 2, 8, 6, 3, 7, 1, 4"}->{"2, 3, 1, 4","5","8, 6, 7"}
{"2, 3, 1, 4"}->{"1","2","3, 4"}
{"8, 6, 7"}->{"6, 7","8"}
{"3, 4"}->{3,4}{"6, 7"}->{6,7}
}
```
在實作時，`Quick sort` 還有一個特點是：**它不需要多餘的記憶體來儲存左/右數列**
可以靠數學方法解決：
1. 將「比對基準數」放在數列第一位 (也可以直接選數列第一位當基準)
2. 記錄當前右陣列的第一數的位置 (初始值設為數列的第二位)
3. 每當出現應擺在左陣列的數，和右陣列的第一位交換位置並更新右陣列的第一數位置
4. 處理完整個數列後，將左數列最後一項和第一項位置交換
:::spoiler `code`
```cpp=
void quick_sort(vector<LL>& v, int i, int j) {
if (j - i >= 1) {
swap(v[i], v[int(i + j) / 2]);//取數列中間項為基準
int left = i;
for (int x = i + 1; x < j; x++) {
if (v[x] <= v[i]) swap(v[left + 1], v[x]),left++;
}
swap(v[i], v[left]);
quick_sort(v, i, left), quick_sort(v, left + 1, j);
}
else return; //其實這行可以不用打
}
```
:::
但要注意，**`Quick sort` 的複雜度有時候會暴增**
看看以下範例：
```graphviz
digraph main{
node[color="black" fontcolor="black" fontname="Arial"]
edge[color="black" fontcolor="black"]
fontname=""
{"5, 2, 8, 6, 3, 7, 1, 4"}->{"1","5, 2, 8, 6, 3, 7, 4"}
{"5, 2, 8, 6, 3, 7, 4"}->{"5, 2, 6, 3, 7, 4", "8"}
{"5, 2, 6, 3, 7, 4"}->{"5, 2, 6, 3, 4", "7"}
{"5, 2, 6, 3, 4"}->{"2", "5, 6, 3, 4"}{"5, 6, 3, 4"}->{"3","5, 6, 4"}{"5, 6, 4"}->{"4", "5, 6"}{"5, 6"}->{5, 6}
}
```
假設今天就是這麼衰，每次都挑到數列中最大或最小的數，那麼 `Quick sort` 就會變得非常慢。
`Time Complexity` : $O(NlgN)$ ~ $O(N^2)$
## 小結
所以 `Merge sort` 雖然比正常情況下的 `Quick sort` 慢，但是**它很穩定**
所以解題時一般情況都建議使用 `Merge sort`
當然，如果可以使用內建 `sort` 優先用內建的！
---
## 補充：Radix Sort (基數排序法)
假設今天處理的數列是：
|274|369|501|487|63|446|871|228|
|-|-|-|-|-|-|-|-|
我們先對「個位數」做排序 $\Rightarrow$
|501|871|63|274|446|487|228|369|
|-|-|-|-|-|-|-|-|
然後對「十位數」做排序 $\Rightarrow$
|501|228|446|63|369|871|274|487|
|-|-|-|-|-|-|-|-|
接著是「百位數」 (沒有百位數的就補零) $\Rightarrow$
|63|228|274|369|446|487|501|871|
|-|-|-|-|-|-|-|-|
因為本數列最大就到百位數，排序完成！
當然，你要從百位數做到個位也沒問題
### 實作
可以建 `vector<vector<type>>`，
第一維度的大小是 「數字要分幾組」，
例如向範例以十進位分就是分十組，實作時通常是取 16 進位
而第二維度的長度就取決於每一組有多少數字啦~
:::spoiler `code`
```cpp=
void radix_sort(vector<LL>& v) {
vector<vector<LL>> bkt(16, vector<LL>());
LL k = 0; unsigned LL filter = 15; int n = 0;
while (bkt[0].size() < v.size()) {
n = 0;
for (size_t x = 0; x < v.size(); x++) {
bkt[(v[x] & filter) >> (k << 2)].push_back(v[x]);
}
for (int x = 0; x < 16; x++) {
for (size_t y = 0; y < bkt[x].size(); y++)
v[n] = bkt[x][y], n++;
if (bkt[x].size() != v.size()) bkt[x].clear();
}
filter <<= 4;
k++;
}
}
```
:::
`Time Complexity`：$O(N\log_m N)$，$m =$ 分組組數
Sign in with Wallet
Connect another wallet