今天介紹插入排序法&快速排序法~~
主題還是希望圍繞在實戰刷題，畢竟刷題的時候有需要排序大多是調用函式的..所以今天介紹這兩個排序法主要是因為解題常用到與實現演算法類似的操作。明天的Merge Sort就會有實際的例題了!!

插入排序法(Insertion Sort)

原理：藉由不斷插入元素進已排序數組來達到整個數組排序。

思考&衍伸：

1. 插入已排序數組時，一般先線性遍歷找到適當的插入位置(要使數組有序)，找到前不斷將數組右移(為了使數插入)
   • 讓插入時，後面的數字右移該何實現? 向左遍歷，向右移動
2. 但插入排序有在遍歷到索引i時，i-1已經排序了的特性，故可以考慮使用二分搜尋去優化，其效率為O(Nlog(N))，可以說是利用相對直觀的方式去讓時間複雜度降至O(nlog(n))
3. 關於二分搜尋的更多細節(之後系列文章也會介紹)：
   https://coliru.stacked-crooked.com/a/615975e64f41d88d

一般的插入排序

void insertion_sort(vector<int>& arr){
    for(int i = 1; i<arr.size(); ++i){
        int curr = arr[i];
        int j;
        for(j = i-1; j>=0; j--){
            if(curr<arr[j])
                arr[j+1] = arr[j]; //右移
            else{
                break;
            }
        }
        arr[j+1] = curr;
    }
}

插入排序加入二分搜尋

void insertion_sort_bin(vector<int>& arr){
    for(int i = 1; i<arr.size(); ++i){
        int curr = arr[i];
        int f = 0, b = i-1;
        // find
        while(b>=f){
            int mid = (b+f)/2;
            if(arr[mid]>curr){
                b = mid-1;
            }
            else{
                f = mid+1;
            }
        } 
        for(int j = i-1; j<=f; --j){
            arr[j+1] = arr[j]; //右移
        }
        arr[f] = curr;
    }
}

運用STL函式

lower_bound( begin,end,num)從陣列的begin位置到end-1位置二分查詢第一個大於或等於num的數字，找到返回該數字的地址，不存在則返回end。通過返回的地址減去起始地址begin,得到找到數字在陣列中的下標。
連結

void insertion_sort_bin(vector<int>& arr){
    for(int i = 1; i<arr.size(); ++i){
        int curr = arr[i];
        int f = lower_bound(arr.begin(),arr.begin()+i, curr)-arr.begin();
        for(int j = i-1; j<=f; --j){
            arr[j+1] = arr[j]; //右移
        }
        arr[f] = curr;
    }
}

快速排序(QuickSort)

原理：反覆將數組分成以一個基準數k分割大於k的放到一側，小於k的放到一側，以左右兩側作子數組分治求解(基準點其實可以隨意選擇，但為了好實現就選擇最右側的數。

思考&衍伸：

1.分治求解的思路，與MergerSort類似
2.將最右側的數作為基準，是簡化實現的好方法!!!
3.時間複雜度O(nlogn)

void quick_sort(vector<int>& arr, int l, int r){
    if(arr.size()==1){
        return;
    }
    if(l>=r){
        return;
    }
    int pivot = arr[r];
    int s = l;
    
    //大於基準的放一邊，小於基準的放一邊
    for(int i = l; i<=r; ++i){
        if(arr[i]<pivot){
            swap(arr[s], arr[i]);
            s++;
        }
    }
    swap(arr[s], arr[r]);
    quick_sort(arr, l, s-1);
    quick_sort(arr, s+1, r);
    
}

((明天會介紹Merge Sort))