# 演算法十八般武藝
搜尋演算法
---
題目簡述：[LeetCode278 First Bad Version](https://leetcode.com/problems/first-bad-version/description/)
透過題目提供的函數查詢最小的損壞版本（尋找下限）
> 前言：這兩個為最基本的搜尋演算法，所以不想詳細說明原理，以下用這張圖簡單說明操作過程
### 線性搜尋法（Sequential Search）
```cpp=
long long firstBadVersion(long long n) {
long long left = 1, right = n;
while(left < right){
if(isBadVersion(left)) return left;
else left ++;
};
return left;
}
```
* 原理簡述：逐一資料校對，直到找到正確資料，否則輸出無
* 時間複雜度：$O(n)$
* TLE 原因分析：資料數過多，程式效率不夠
* LeetCode 結果圖：
---
### 二元搜尋法（Binary Search）
```cpp=
long long firstBadVersion(long long n) {
long long left = 1, right = n;
while(left < right){
long long mid = (left + right) / 2;
if(isBadVersion(mid)) right = mid;
else left = mid + 1;
};
return left;
}
```
* 原理簡述：利用先排序好的優勢，可以快速判斷被查詢數的範圍
* 時間複雜度：$O(logn)$
* AC 原因分析：由於是透過比大小的概念，所以能快速過濾不需比較的部分
* LeetCode 結果圖：
排序演算法
---
題目簡述：[LeetCode912 Sort An Array](https://leetcode.com/problems/sort-an-array/)
就是排序，但是基本上要 $O(nlogn)$ 才能通過
> 前言：
> 交換，插入，選擇，快速，合併排序法皆為比較型排序法。只有最後兩者能有機會將複雜度壓到 $O(nlogn)$。
>
> 計數，桶，基數排序法為非比較型排序。根據資料特性，能成功突破 $O(nlogn)$ 限制。
### 交換排序法（Bubble Sort）
```cpp=
vector<int> sortArray(vector<int>& nums) {
for(int i = nums.size()-1; i>=0; i--){
for(int j = 0; j<=(i-1);j++){
if(nums[j] > nums[j+1]) swap(nums[j], nums[j+1]);
}
}
return nums;
}
```
* 原理簡述：透過兩兩比大小並交換，能保證每一回有元素被正確安放
* 時間複雜度：$O(n^2)$
* TLE 原因分析：資料量過多，排序效率不夠
* LeetCode 結果圖：
---
### 插入排序法（Insertion Sort)
```cpp=
vector<int> sortArray(vector<int>& nums) {
int i, j, tmp;
for(i = 1; i < nums.size(); i++){
tmp = nums[i];
j = i - 1;
while(j >= 0 && nums[j] > tmp){
nums[j+1] = nums[j];
j --;
}
nums[j + 1] = tmp;
}
return nums;
}
```
* 原理簡述：過程中會有兩部分，一部分是排序好的（前），一部分為未排序的（後）。將未排序的資料一一拿出並插入合適的位置。
* 時間複雜度：$O(n^2)$
* TLE 原因分析：同上，資料數過多
* LeetCode 結果圖：
---
### 選擇排序法（Selection Sort）
```cpp=
vector<int> sortArray(vector<int>& nums) {
for(int i = 0; i < nums.size() - 1; i++){
for(int j = i + 1; j < nums.size(); j++){
if(nums[j] < nums[i]) swap(nums[i], nums[j]);
}
}
return nums;
}
```
* 原理簡述：選出當前最小的資料並於最前頭交換
* 時間複雜度：$O(n^2)$
* TLE 原因分析：同上，資料數過多
* LeetCode 結果圖：
---
### 快速排序法（Quick Sort）
```cpp=
void quickSort(vector<int>& nums, int l, int r){
if(l >= r) return;
int low = l + 1, high = r;
int pivot = nums[l];
while(true){
while(low < nums.size() && nums[low] < pivot) low ++;
while(high >= 0 && nums[high] > pivot) high --;
if(low < high){
swap(nums[low], nums[high]);
low ++;
high --;
}
else{
high %= nums.size();
swap(nums[high], nums[l]);
break;
}
}
quickSort(nums, l, high - 1);
quickSort(nums, high + 1, r);
return;
}
vector<int> sortArray(vector<int>& nums) {
quickSort(nums, 0, nums.size() - 1);
return nums;
}
```
* 原理簡述：
1. 任意選擇一個資料當作基準值
2. 將剩餘資料一一比較，較大者放於右方，較小者放於左方
3. 重新選擇基準值，通常先選左再選右
4. 重複上述三個步驟，直到沒有基準值可用
* 時間複雜度：
* 最好：$O(nlogn)$
* 最差：$O(n^2)$
* TLE 原因分析：由於遇到最差狀態的測資，所以變成複雜度變成$O(n^2)$，使得程式效率變差
* LeetCode 結果圖：
---
### 合併排序法（Merge Sort）
```cpp=
void merge(vector<int>& nums, vector<int>& v1, vector<int>& v2){
int i = 0, j = 0, k = 0;
while(i < v1.size() && j < v2.size()){
if(v1[i] < v2[j]) nums[k++] = v1[i++];
else nums[k++] = v2[j++];
}
while(i < v1.size()) nums[k++] = v1[i++];
while(j < v2.size()) nums[k++] = v2[j++];
}
void mergeSort(vector<int>& nums){
if(nums.size() <= 1) return;
vector<int> v1(nums.begin(), nums.begin() + (nums.size() >> 1));
vector<int> v2(nums.begin() + (nums.size() >> 1), nums.end());
mergeSort(v1);
mergeSort(v2);
nums.assign(nums.size(), 0);
merge(nums, v1, v2);
}
vector<int> sortArray(vector<int>& nums) {
mergeSort(nums);
return nums;
}
```
* 原理簡述：
1. 先將全部資料拆成一個單位
2. 依序比較大小合併
* 時間複雜度：$O(nlogn)$
* AC 原因分析：合併排序法主要是透過 n 次的拆解，在進行 log~2~n 次的合併，使得最複雜的測資剛好能在時間限制內完成
* LeetCode 結果圖：
---
### 計數排序法 （Count Sort）
```cpp=
void countSort(vector<int>& A, vector<int>& B, vector<int>& C){
for(int i=0;i<A.size();i++) B[A[i] + 5e4]++;
for(int i=1;i<B.size();i++) B[i] += B[i-1];
for(int i= A.size() - 1; i>=0; i--){
C[B[A[i] + 5e4] - 1] = A[i];
B[A[i] + 5e4]--;
}
}
vector<int> sortArray(vector<int>& nums) {
vector<int> B(1e5 + 2, 0);
vector<int> C(nums.size(), 0);
countSort(nums, B, C);
return C;
}
```
* 原理簡述：
1. 創建測資範圍的陣列，並逐一將資料放入
2. 前綴累計每種資料的數量
3. 根據第二點統計結果依序將資料放入合適位置
* 時間複雜度：
* $O(n+b)$
> b：輸入範圍
> n：資料量
* AC 原因分析：此次結果根據資料特性做分類，因此能加快重複種類的資料排序的效率，使得最複雜測資通過
* LeetCode 結果圖：
---
### 桶排序（Bucket Sort）
```cpp=
void bucketSort(vector<int> &nums){
int n = nums.size();
vector<vector<int>> bucket(1e5 + 1);
for(int i = 0; i < n; i++) bucket[nums[i] + 5e4].push_back(nums[i]);
int k = 0;
for(int i = 0; i < bucket.size(); i++){
sort(bucket[i].begin(), bucket[i].end());
int size = bucket[i].size();
for(int j = 0; j < size; j++) nums[k++] = bucket[i][j];
}
}
vector<int> sortArray(vector<int>& nums) {
bucketSort(nums);
return nums;
}
```
* 原理簡述：
1. 分個資料範圍並分配成數個桶
2. 依序將每個資料放進合適的桶中
3. 使用任意排序法排序桶內資料
4. 依序將桶中的資料排出
* 時間複雜度：
* 一般情況：$O(nlog(n / m))$
> 詳計：m * O(k * logk) = m * O((n / m)*log(n / m)) = O(nlog(n / m))
> m：桶數量
> n：資料量
> k：n / m
* 最好情況：$O(n)$
> 若 m 接近 n , 則 n / m 為較小常數
* AC 原因分析：因桶數量接近資料量，使得複雜度接近一次的線性排序結果 $O(n)$，因而成功壓縮時間
* 備註： 此種作法非常消耗空間需求，也容易受桶中內置排序法的複雜度影響
* LeetCode 結果圖：
{
int n = nums.size();
vector<vector<int>> bucket(10);
for(int i = 0; i < n; i++) bucket[nums[i] / (1 * t) % 10].push_back(nums[i]);
int k = 0;
for(int i = 0; i < 10; i++){
sort(bucket[i].begin(), bucket[i].end());
int size = bucket[i].size();
for(int j = 0; j < size; j++) nums[k++] = bucket[i][j];
}
}
void RadixSort(vector<int> &nums){
for(int i=0;i<nums.size();i++) nums[i] = nums[i] + 5e4;
int t = 1;
while(t <= 100000){
bucketSort(nums, t);
t *= 10;
}
for(int i=0;i<nums.size();i++) nums[i] = nums[i] - 5e4;
}
vector<int> sortArray(vector<int>& nums) {
RadixSort(nums);
return nums;
}
```
* 原理簡述：
1. 創建 0~9 的桶子
2. 依序將資料比較個位的數字，並放入適當桶中
3. 依序將桶中資料排出
4. 重複前三步動作，但用於比較的位數逐漸往前移直到最大位數
* 時間複雜度：
* $O(d(n+r))$
> r：基數
> n：測資量
> d：執行回合數
* AC 原因分析：最差情況由於總共只需比較五次，因此能將最差結果複雜度視為 $O(5n + 25)$，此外由於 25 遠小於 5n，主要的時間複雜度為 $O(5n)$，成功壓縮時間。
* 備註：基數排序法的每次回合的排序方法通常使用桶排序或計數排序，並根據資料性質決定基數性質，來達到此種非比較性的排序法。
* LeetCode 結果圖：
---
### C++ STL sort 排序
```cpp=
vector<int> sortArray(vector<int>& nums) {
sort(nums.begin(), nums.end());
return nums;
}
```
* 原理簡述：
* STL 的 sort 算法， 數據量大時採用快速排序，分段遞迴排序。一旦分段后的數據量小於某個門檻，為避免快速排序的遞迴調用帶來過大的额外負荷，就改用插入排序。如果遞迴層次過深，還會改用堆積排序
* 簡單來說：
* 一般情況：快速排序
* 簡單情況：插入排序
* 複雜情況：堆積排序
* 此外此排序法會依據資料結構分配較適當的排序演算法
* 備註，若為關聯式容器，建議不要使用這個 sort 工具，因為關聯式容器其底層已包含自動排序演算法，所以沒必要再排序一次
* 時間複雜度：
* 依排序容器與數據情況為不同複雜度時間
* 最好情況為 $O(1)$
* AC 原因分析：因為他太強大了
* LeetCode 結果圖：
* 資料來源：[C++ STL sort 分析](https://blog.csdn.net/u011386173/article/details/110394829)
Sign in with Wallet
Connect another wallet