---
tags: Coding
---
# 分治
## qsort (快速排序) 原理
### [參考文章出處](http://alrightchiu.github.io/SecondRound/comparison-sort-quick-sortkuai-su-pai-xu-fa.html)
**分治的精神: 把大問題拆成小問題**
要排序我們可以隨便選一個數字，然後把陣列左右分成小於這個數的部分放左邊，與大於這個數的不分放右邊。我們再從左部分做同樣的事，右部分也做同樣的事。

**分堆的方法:**
為了方便我們取最後一個數當作基準點。然後設立兩個變數i、j。j負責查看第一個到倒數第二個數有沒有小於最後一個數(基準點)。i先設成第一個數-1(front-1)。j從第一個看，每當有數字小於基準點就i++然後array[i]與array[j]交換。最後j都看完全部數後array[i]與array[end](基準點)交換數值。此時i就是基準點的位置。

**因此我們可以歸納出:**
分堆(partition)=>1.比中數小的左堆分堆 2.比中數大的右堆分堆
直到剩下一個數不能分就停止回去執行別的遞迴

#include<bits/stdc++.h>
using namespace std;
void PrintArray(int *a,int n){
    for(int i=0;i<n;i++)cout<<a[i]<<" ";
    cout<<endl;
}
int Partition(int *a,int f,int e){//front and end
    int i=f-1;
    for(int j=f;j<e;j++){
        if(a[j]<a[e]){
            i++;
            swap(a[j],a[i]);
        }
    }
    i++;
    swap(a[e],a[i]);
    PrintArray(a,8);/
    return i;
}

/*
int last;
int Partition(int *a,int f,int e){//front and end
    last = a[e];
    partition(a+f,a+e,[](int k){ return k<last;});
    int i=partition_point(a+f,a+e,[](int k){ return k<last;})-a;
    swap(a[e],a[i]);
    return p;
}*/
//用c++的partition函示一樣可以達到同樣效果

void Quick_sort(int *a,int f,int e){//front and end
    if(f<e){
        int pivot=Partition(a,f,e);
        Quick_sort(a,f,pivot-1);
        Quick_sort(a,pivot+1,e);
    }
}
signed main () {
    int arr[]={8,4,5,6,3,7,2,1};
    int n=sizeof(arr)/sizeof(int);
    cout<<"before: ";
    PrintArray(arr,n);
    Quick_sort(arr,0,n-1);
    cout<<"after: ";
    PrintArray(arr,n);
    return 0;
}

## Merge Sort 原理
### [參考文章出處](http://alrightchiu.github.io/SecondRound/comparison-sort-merge-sorthe-bing-pai-xu-fa.html)
**分治:**
我們把陣列一直對半分開直到不能續切為止。接著我們再把每一小堆依照順序大小組合，從最小堆的慢慢組合到本的長度。

**組合 Merge:**
主要目地把左推(left)與右推(right)組合在一起，但要注意的是左堆與右堆都要已經被排序好了。這部分用vector實做比較方便，首先先在複製一個左右堆，並在最後都放入無限大的數字保證不會有數字超過無限大，像是INT_MAX。接著i代表左堆中的位置，j代表右堆中的位置，兩個初始值都是0。然後我們比較left[i]與right[j]的大小。誰比較小就放入陣列中，小的那個i或j就+1，表示看到下一個數，最後比到left[i]跟right[j]都是最後一個數INT_MAX。

**簡單來說:**
就是分分分分分到不能分 再合合合合合到原本的大小


#include<bits/stdc++.h>
using namespace std;
void PrintArray(int *a,int n){
    for(int i=0;i<n;i++)cout<<a[i]<<" ";
    cout<<endl;
    return;
}
void Merge(int *a,int f,int e,int mid){
    vector<int>Left(a+f,a+mid+1);
    vector<int>Right(a+mid+1,a+e+1);
    Left.push_back(INT_MAX);
    Right.push_back(INT_MAX);
    int left_idx=0,right_idx=0;
    for(int i=f;i<=e;i++){
        if(Left[left_idx]<=Right[right_idx]){
            a[i]=Left[left_idx];
            left_idx++;
        }else if(Left[left_idx]>Right[right_idx]){
            a[i]=Right[right_idx];
            right_idx++;
        }
    }
    //PrintArray(a,8);看看過程(除錯用)
    return;
}
void Merge_sort(int *a,int f,int e){
    int mid=(f+e)/2;
    if(f<e){
        Merge_sort(a,f,mid);
        Merge_sort(a,mid+1,e);
        Merge(a,f,e,mid);
    }
    return;
}
signed main () {
    int arr[]={8,2,5,1,3,7,6,4};
    int n=sizeof(arr)/sizeof(int);
    cout<<"before: ";
    PrintArray(arr,n);
    Merge_sort(arr,0,n-1);
    cout<<"after: ";
    PrintArray(arr,n);
    return 0;
}