---
# System prepended metadata

title: 演算法十八般武藝

---

# 演算法十八般武藝


搜尋演算法
---
題目簡述：[LeetCode278 First Bad Version](https://leetcode.com/problems/first-bad-version/description/)
    透過題目提供的函數查詢最小的損壞版本（尋找下限） 
> 前言：這兩個為最基本的搜尋演算法，所以不想詳細說明原理，以下用這張圖簡單說明操作過程
![搜尋法比較](https://i.imgur.com/0J99Mll.gif)

### 線性搜尋法（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 結果圖：
    ![線性搜尋結果](https://i.imgur.com/D9Dgvoi.png)
---

### 二元搜尋法（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 結果圖：
    ![二元搜尋結果](https://i.imgur.com/0q38SrP.png)


排序演算法
---
題目簡述：[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;
}
```
* 原理簡述：透過兩兩比大小並交換，能保證每一回有元素被正確安放
  ![氣泡排序動畫](https://i.imgur.com/CDTEYA4.gif)
* 時間複雜度：$O(n^2)$
* TLE 原因分析：資料量過多，排序效率不夠
* LeetCode 結果圖：
    ![交換排序結果](https://i.imgur.com/oON1dse.png)
---

### 插入排序法（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;
}
```
* 原理簡述：過程中會有兩部分，一部分是排序好的（前），一部分為未排序的（後）。將未排序的資料一一拿出並插入合適的位置。
  ![插入排序動畫](https://i.imgur.com/QZyEK0o.gif)
* 時間複雜度：$O(n^2)$
* TLE 原因分析：同上，資料數過多
* LeetCode 結果圖：
    ![插入排序結果](https://i.imgur.com/AL5Ih66.png)
---

### 選擇排序法（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;
}
```
* 原理簡述：選出當前最小的資料並於最前頭交換
  ![選擇排序動畫](https://i.imgur.com/OxjkHow.gif)
* 時間複雜度：$O(n^2)$
* TLE 原因分析：同上，資料數過多
* LeetCode 結果圖：
    ![選擇排序結果](https://i.imgur.com/FJaARAK.png)
---

### 快速排序法（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. 重複上述三個步驟，直到沒有基準值可用
  ![快速排序動畫](https://i.imgur.com/mJa0lnh.gif)
* 時間複雜度：
    * 最好：$O(nlogn)$
    * 最差：$O(n^2)$
* TLE 原因分析：由於遇到最差狀態的測資，所以變成複雜度變成$O(n^2)$，使得程式效率變差
* LeetCode 結果圖：
    ![快速排序結果](https://i.imgur.com/gkIUdEA.png)
---

### 合併排序法（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. 依序比較大小合併
  ![合併排序動畫](https://i.imgur.com/CmF89La.gif)
* 時間複雜度：$O(nlogn)$
* AC 原因分析：合併排序法主要是透過 n 次的拆解，在進行 log~2~n 次的合併，使得最複雜的測資剛好能在時間限制內完成
* LeetCode 結果圖：
    ![合併排序結果](https://i.imgur.com/g6P47Mg.png)
---

### 計數排序法 （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. 根據第二點統計結果依序將資料放入合適位置
    ![計數排序動畫](https://i.imgur.com/VkuFWt1.gif)
* 時間複雜度：
    * $O(n+b)$
        > b：輸入範圍
        > n：資料量
* AC 原因分析：此次結果根據資料特性做分類，因此能加快重複種類的資料排序的效率，使得最複雜測資通過
* LeetCode 結果圖：
    ![計數排序結果](https://i.imgur.com/gqwAIEn.png)
---

### 桶排序（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. 依序將桶中的資料排出
    ![桶排序動畫](https://i.imgur.com/m4PnwmX.gif)


* 時間複雜度：
    * 一般情況：$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 結果圖：
    ![桶排序結果](https://i.imgur.com/
---

### 基數排序法（Radix Sort）
```cpp=
void bucketSort(vector<int>& nums, int t){
    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. 重複前三步動作，但用於比較的位數逐漸往前移直到最大位數
  ![基數排序動畫](https://i.imgur.com/v4nDzBW.gif)

* 時間複雜度：
    * $O(d(n+r))$
        > r：基數
        > n：測資量
        > d：執行回合數
* AC 原因分析：最差情況由於總共只需比較五次，因此能將最差結果複雜度視為 $O(5n + 25)$，此外由於 25 遠小於 5n，主要的時間複雜度為 $O(5n)$，成功壓縮時間。
* 備註：基數排序法的每次回合的排序方法通常使用桶排序或計數排序，並根據資料性質決定基數性質，來達到此種非比較性的排序法。
* LeetCode 結果圖：
    ![基數排序結果](https://i.imgur.com/6n1AFct.png)
---

### 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://i.imgur.com/GzE2aE6.png)
* 資料來源：[C++ STL sort 分析](https://blog.csdn.net/u011386173/article/details/110394829)


