DAY2 - 排序(一)

今天介绍插入排序法&快速排序法~~
主题还是希望围绕在实战刷题，毕竟刷题的时候有需要排序大多是调用函式的..所以今天介绍这两个排序法主要是因为解题常用到与实现演算法类似的操作。明天的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))