查找
Linear Search
使用迴圈，從第一個開始逐一尋找目標值，到下列兩狀況之一時停止搜尋：
- 找到目標值。
- 搜尋完全部資料仍未找到目標值。
代码：
int LinearSearch(const vector<int>& arr, int n) {
for (int i=0, i < arr.size(), i++)
if (arr[i] == n) return i; //找到數值與n相符者，回傳其所在索引值
return -1;
}時間複雜度
最糟情況：O(n)，即目標值在最後一格，要走過每筆資料才能找到。
最佳情況：O(1)，即目標值在第一格，一找就找到。
平均情況：O(n/2)=O(n)。
空間複雜度
O(1)，僅在原陣列內搜尋，不需額外的空間暫存資料。
是在位的！
Binary Search
僅適用於已經按照大小順序排好的資料，每次搜尋時將資料對半切，看目標值在左半邊或右半邊，直到找到目標值為止。
详解
参考例题：给定一个升序数组，找到 target 第一次出现的位置和最后一次出现的位置。
// 示例：
nums = [5,7,7,8,8,10]
target = 8
// 结果：
[3,4]
// 如果不存在：
[-1,-1]代码：
int lower_bound(vector<int>& nums, int target) {
int left = -1, right = nums.size();
while (left+1 < right) {
int mid = (left+right)/2;
if (nums[mid] < target)
left = mid;
else right = mid; // mid >= target
}
return right;
}泛式 (板子)：
int left = -1, right = nums.size();
while (left+1 < right) {
int mid = (left+right)/2;
if (nums[mid] < target)
left = mid;
else right = mid; // mid >= target
}
if (right < nums.size() && nums[right] == target)
return right;
return -1;時間複雜度!!!
- 最差情況：O(log n)，即目標值在頭尾或緊鄰切第一刀處，要找尋 log₂ n 次，時間複雜度為 O(log₂ n)=O(log n)。
- 最佳情況：O(1)，即目標資料切第一刀處，一找就找到。
- 平均情況：O(log₂ n)=O(log n)。
空間複雜度!!!
視實際執行方式而異：
- 迴圈法：O(1)，僅在原陣列內劃定範圍並進行比較、搜尋，不需額外儲存空間。
- 遞迴法：O(log n)，需要額外空間儲存遞迴過程產生的堆疊（stack）。
排序!!!
氣泡排序、插入排序、選擇排序是三種概念較簡單的排序方式，空間複雜度皆僅要 O(1)，但平均時間複雜度皆達 O(n²)，除非要處理的資料量少，否則實務上少有應用。
Bubble Sort
由後而前依序將兩兩相鄰的值互相比較，直到所有的值都被排到正確的位置為止。
CODE
#include <algorithm>
void bubbleSort(vector <int>& arr) {
for (int i=0; i<=arr.size()-2; ++i) {
for (int j=arr.size()-1; j>=(i+1); --j) {
if (arr[j-1] > arr[j]) {
std::swap(arr[j-1], arr[j]);
}
}
}
}時間複雜度
氣泡排序使用雙層巢狀迴圈（nested loop），外層 i 從第 0 項走到 (arr.length-2) 項（次末項），在 i 之前的值代表已經排序好的資料；內層 j 從第 (arr.length-1) 項（最末項）開始走到第 (i+1) 項，用來將相鄰的值兩兩配對比較。現假設陣列中共有 (n+1) 筆資料（索引值從 0 到 n），時間複雜度分析如下：
- 最差情況：O(n²)，若原陣列排序正好與目標順序完全相反，所有的值都被調換，最末項調換 n 次、次末項調換 (n-1) 次…第 1 項調換 1 次、第 0 項調換 0 次，全部共調換 [n+(n-1)+…+1+0] = [(n+0)*(n+1)]/2 = (n²+n)/2 次，O((n²+n)/2)=O(n²)。
- 最佳情況：O(n)，若原陣列排序正好與目標順序完全相同，即 i 從第 0 項走到次末項，內層 j 的項目不需要執行，因此一共只有 (n-1) 個運算步驟，時間複雜度為 O(n)。
- 平均情況：O(n²)，因使用巢狀迴圈，因此多數情況下會有 n*n 個運算步驟。
空間複雜度
O(1)，在排序過程中，資料只在原陣列當中比較、調換，需要的儲存空間固定，不需額外空間暫存資料（在位）。
Insertion Sort
CODE
void insertionSort(vector <int>& arr) {
for (int flag=1; flag<arr.size(); ++flag) {
int key = arr[flag], e = flag - 1;
while (e>=0 && arr[e]>key) {
arr[e+1] = arr[e]; // 重点！！！
--e;
}
arr[e+1] = key; //??
}
}为什么是arr[e+1] = arr[e]？
虽然e = flag - 1，但是arr[flag]被key利用，只能从不断变化的被比较值arr[e]及其后一位arr[e+1]入手.
時間複雜度
選擇排序使用雙層巢狀迴圈（nested loop），外層 j 從第 1 項走到 (arr.length-1) 項（最末項），在 j 之前的資料代表已經當過「key」；內層 i 從第 (j-1) 項開始走到第 (-1) 項，用來將資料中所有的值逐一跟「key」比較，以找出「key」的正確位置。現假設陣列中共有 (n+1) 筆資料（索引值從 0 到 n），時間複雜度分析如下：
- 最差情況：O(n²)，若原陣列排序正好與目標順序完全相反，所有的值都被調換，第 0 項調換 1 次、第 1 項調換 2 次…次末項調換 (n-1) 次、最末項調換 n 次，全部共調換 [1+2…+(n-1)+n] = [(1+n)*n]/2 = (n+n²)/2次，O((n+n²)/2)=O(n²)。
- 最佳情況：O(n)，若原陣列排序正好與目標順序完全相同，即 j 從第 1 項走到最末項，內層迴圈比較 i 與「key」不需執行，因此一共只有 (n-1) 個運算步驟，時間複雜度為 O(n)。
- 平均情況：O(n²)，因使用巢狀迴圈，因此多數情況下會有 n*n 個運算步驟。
空間複雜度
在位，O(1)。
Selection Sort
在所有資料值中，依序找出最符合目標條件者先排，直到每筆資料都被放到正確的位置為止。 
原理
伪析解
CODE
#include <algorithm>
void selectionSort(vector <int>& arr) {
for (int i=0; i<=arr.size()-2; ++i) {
int min = i;
for (int j=i+1; j<=arr.size()-1; ++j)
if (arr[j] < arr[min]) min = j;
std::swap(arr[i], arr[min]);
}
}時間複雜度
- 最差情況：O(n²)
- 最佳情況：O(n)
- 平均情況：O(n²)
空間複雜度
在位，O(1)。
小结
Merge Sort
Leetcode.148:给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
e.g.
CODE(投机)
ListNode* sortList(ListNode* head) {
std::vector<int> arr;
Listnode* p = head;
// copy list to arr
while (p != nullptr) {
arr.push_back(p->val);
p=p->next; // p is moving!
}
// sort arr
std::sort(arr.begin(), arr.end());
// copy sorted arr to list
p = head;
int i = 0;
while(p != nullptr) {
p->val=arr[i++];
p=p->next;
}
return head;
}