---
# System prepended metadata

title: 分治
tags: [Coding]

---

---
tags: Coding
---
# 分治
## 大數演算法
### 原本 O(n^2)
![02_divide_n_conquer](https://hackmd.io/_uploads/B1NQoL6sJg.jpg =80%x)
### 優化版 O(lg3)=O(n^1.58)
```c=
function prod2(u, v):
    if u == 0 or v == 0 then
        return 0
    
    n = max(length of u, length of v)

    if n ≤ threshold then
        return u * v
    
    m = floor(n / 2)
    
    x = u / 10^m   // 高位部分
    y = u % 10^m   // 低位部分
    w = v / 10^m   // 高位部分
    z = v % 10^m   // 低位部分
    
    r = prod2(x + y, w + z)  // 計算兩個部分總和的乘積
    p = prod2(x, w)          // 計算高位部分的乘積
    q = prod2(y, z)          // 計算低位部分的乘積

    return p * 10^(2m) + (r - p - q) * 10^m + q
```

![image](https://hackmd.io/_uploads/HkAVqU6ikx.png =80%x)
![image](https://hackmd.io/_uploads/rJBu58ai1g.png =80%x)
![image](https://hackmd.io/_uploads/ByLKcL6skl.png =80%x)
![image](https://hackmd.io/_uploads/rkAcqL6jyx.png =80%x)

## 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.比中數大的右堆分堆
直到剩下一個數不能分就停止回去執行別的遞迴
![](https://raw.githubusercontent.com/alrightchiu/SecondRound/master/content/Algorithms%20and%20Data%20Structures/Sorting%20series/ComparisonSort_fig/QuickSort/f13.png =400x)

```cpp=
#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。

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

![](https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/Sorting%20series/ComparisonSort_fig/MergeSort/f1.png?raw=true =400x)
```cpp=
#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;
}
```