---
# System prepended metadata

title: 排序和搜尋法
tags: [進階班]

---

---
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 =$ 分組組數