分治法的思想

將原問題分解為幾個規(guī)模較小但類似于原問題的子問題，遞歸地求解這些子問題，然后再合并這些子問題的解來建立原問題的解。

分治模式的步驟

1. 分解原問題為若干子問題；

2. 解決子問題；

3. 合并子問題的解，形成原問題的解。

歸并排序算法

歸并排序算法就是使用了分治的思想。

算法步驟

1. 分解：將待排序的\(n\)個元素的序列分解成各具有\(\frac{n}{2}\)個元素的兩個子序列；

2. 解決：使用歸并排序遞歸地排序兩個子序列；

3. 合并：合并兩個已排序好的子序列，最終產(chǎn)生已排序的答案。

注意事項

1. 當遞歸到子序列的長度為1時，無需再分解，與對應的子序列合并。因為長度為1的序列可以視為已排序好的序列，即已解決。

2. 函數(shù)名聲明：下文中，MergeSort()表示歸并排序的函數(shù)，Merge()表示輔助函數(shù)，即實現(xiàn)合并步驟的函數(shù)。

偽代碼

歸并排序MergeSort()

//arr: 待排序的序列（始終為原始主序列）
//head: 第一個元素的下標
//tail: 最后一個元素的下標
//length: 當前(子)序列的長度
MergeSort(arr, head, tail, length){
//特殊情況：長度為1
    //此時是終止條件：當?shù)谝粋€元素和最后一個元素是同一個元素
    //說明遞歸到此時的子序列是一個長度為1的序列，直接返回。
    if(head == tail)return

//常規(guī)處理步驟：分解、解決、合并
    // 分解成兩個子問題
    // 1.計算中點
    mid = (head + tail)/2           
    // 2.已中點為界，前后分為兩個子序列，分別排序
    MergeSort(arr,head,mid,mid-head+1)
    MergeSort(arr,mid+1,tail,tail-mid)    

    // 合并分別排序好后的子序列，形成原問題的解
    Merge(arr,head,mid+1,length)
}

輔助函數(shù): 合并Merge()

// arr: 待排序的序列（始終為原始主序列）
// head1: 第一個子序列的起始下標
// head2: 第二個子序列的起始下標
// length: (子)序列長度，也就是這兩個子序列合并后總的長度
Merge(arr,head1,head2,length){
    //創(chuàng)建一個臨時數(shù)組，用于暫時存放合并后的子序列
    temp[length]    
    //開始合并
    i = head1
    j = head2
    while(i<=子序列1尾部 && j<=子序列2尾部){
        // 兩個子序列是分別排序好了的
        // 依次將較小的數(shù)按順序排放在臨時數(shù)組temp中
        // 直到有一個子序列已全部進入temp
        if(arr[i]<arr[j]){
            temp.push(arr[i++])
        }else{
            temp.push(arr[j++])
        }        
    }
    //只要有一個序列排完了，就會跳出上面的循環(huán)
    //接下來就把另一剩下的序列全部排入temp中
    if(i==head2){
        //1.如果i到達第二子序列頭部，說明第二子序列有剩余
        temp.push(rest of subArr2)
    }else{
        //2.這種情況對應：第一子序列有剩余
        temp.push(rest of subArr1)
    }

    // 最后將臨時數(shù)組temp中已排序好的序列，覆蓋掉原始數(shù)組arr中的部分
    // 即完成兩個子序列的合并
    for i=0 to length{
        arr[head1+i] = temp[i]
    }

    //合并完畢
}

歸并排序代碼實例

使用C++實現(xiàn)

函數(shù)聲明

// Merge_sort 歸并排序
void Merge_sort(vector<int> &arr,int head, int tail, int length);
// 歸并排序 中的 合并操作
void Merge(vector<int> &arr, int head1, int head2, int length);

函數(shù)定義

歸并排序

void Merge_sort(vector<int> &arr,int head, int tail, int length){
    if(head != tail){
        // 分解成兩個子問題
        int m = (head + tail)/2;
        // 兩個子問題分別完成操作
        Merge_sort(arr, head, m, m-head+1);
        Merge_sort(arr, m+1, tail, tail-m);
        // 合并兩個子問題的解，得到原問題的解
        Merge(arr, head, m+1, length);
    }
}

輔助函數(shù)：合并

void Merge(vector<int> &arr, int head1, int head2, int length){
    int i = head1;
    int j = head2;
    vector<int> temp;

    while(i<head2 && j<head1+length){
        if(arr[i]<arr[j]){
            temp.push_back(arr[i++]);
        }else{
            temp.push_back(arr[j++]);
        }
    }

    if(i==head2){
        while(j<head1+length){
            temp.push_back(arr[j++]);
        }
    }else{
        while(i<head2){
            temp.push_back(arr[i++]);
        }
    }

    for(int i = 0; i<length; i++){
        arr[i+head1] = temp[i];
    }
}

注意事項

1. arr作為原數(shù)組，任何排序后重寫覆蓋的操作都是對arr直接作用的，作為函數(shù)參數(shù)，應使用引用傳遞.

2. 在合并操作Merge函數(shù)中，length表示當前(子)序列的長度。因此判斷數(shù)組是否遍歷到結尾處的依據(jù)不能是index < length而應該是head1+index < length.