文章目錄

一、什麼是分治算法
二、分治的典型應用
- 應用一：歸并排序
- 應用二：快速排序
- 應用三：輸出前 m 大的數
- 應用四：求排列的逆序數

一、什麼是分治算法

分治算法的基本思想是将一個規模為 N 的問題分解為 K 個規模較小的子問題，這些子問題互相獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解。

一般思路

分解：将要解決的問題劃分成若幹規模較小的同類問題；
求解：當子問題劃分得足夠小時，用較簡單的方法解決；
合并：按原問題的要求，将子問題的解逐層合并構成原問題的解。

算法分析與設計「四」分治算法一、什麼是分治算法二、分治的典型應用

例如下面的找出僞币問題，就是一個典型的分治法應用：

問題描述：16 硬币，有可能有1枚假币，假币比真币輕。有一架天平，用最少稱量次數确定有沒有假币，若有的話，假币是哪一枚。

分治解決：将對 16 個硬币的搜尋問題，轉為對兩組 8 個硬币搜尋的問題。在 8 - 8 個硬币進行稱量，找出較輕的；然後 4 - 4 個硬币稱量，找出較輕的；之後 2 - 2 個稱量，找出較輕的；最後 1 - 1 個稱量，找出較輕的即為假币。

二、分治的典型應用

應用一：歸并排序

歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。其實作排序時的時間複雜度為 O ( n l o g n ) O(nlogn) O(nlogn) 。

思路分析：數組排序任務可以如下完成：① 把前一半排序 ② 把後一半排序 ③ 把兩半歸并到一個新的有序數組，然後再拷貝回原數組，排序完成。參考下圖：

算法分析與設計「四」分治算法一、什麼是分治算法二、分治的典型應用

代碼實作：

#include <iostream>
using namespace std;

int a[8] = {8, 4, 5, 7, 1, 3, 6, 2};
int b[8]; // 用于存放中間結果

// 将兩個半有序數組有序地排到 tmp[] 中，之後拷貝給 a[]。複雜度 O(n)
void Merge(int a[], int s, int m, int e, int tmp[])
{
    int pb = 0;
    int p1 = s, p2 = m + 1;
    while (p1 <= m && p2 <= e)
    {
        if (a[p1] < a[p2])
            tmp[pb++] = a[p1++];
        else
            tmp[pb++] = a[p2++];
    }
    while (p1 <= m)
        tmp[pb++] = a[p1++];
    while (p2 <= e)
        tmp[pb++] = a[p2++];

    // 拷貝回原數組
    for (int i = 0; i < e - s + 1; ++i)
        a[s + i] = tmp[i];
}

// 利用遞歸思想
void MergeSort(int a[], int s, int e, int tmp[])
{
    if (s < e)
    {
        int m = s + (e - s) / 2;     // 中點
        MergeSort(a, s, m, tmp);     // 前段排序
        MergeSort(a, m + 1, e, tmp); // 後段排序
        Merge(a, s, m, e, tmp);      // 歸并
    }
}

int main()
{
    int size = sizeof(a) / sizeof(int);
    MergeSort(a, 0, size - 1, b);
    for (int i = 0; i < size; ++i)
        cout << a[i] << ",";
    cout << endl;
    return 0;
}

歸并排序時間複雜度分析：

算法分析與設計「四」分治算法一、什麼是分治算法二、分治的典型應用

應用二：快速排序

基本思想：

在待排序數組中首先選取一個記錄作為基準（pivotkey），通常選第一個元素。
經過一趟排序，将小于基準的元素放在左側，大于基準的元素放在右側，基準元素放置在分解處。這樣，待排序數組就分成了兩個子表。（需要時間 O ( n ) O(n) O(n))
遞歸地将左側和右側的兩個子表進行排序，直至每個子表隻有一個元素。

具體步驟：

暫時指定第一個記錄為基準，同時附設兩個指針 i，j 分别指向數組的第一個元素和最後一個元素。

算法分析與設計「四」分治算法一、什麼是分治算法二、分治的典型應用
從表的最右側位置依次向左搜尋，找到小于基準的元素，與基準元素進行交換；如果沒有找到，則指針左移。

算法分析與設計「四」分治算法一、什麼是分治算法二、分治的典型應用

算法分析與設計「四」分治算法一、什麼是分治算法二、分治的典型應用
再從數組最左側位置開始，找到大于基準的元素，與基準進行交換；若沒找到，則指針右移。

算法分析與設計「四」分治算法一、什麼是分治算法二、分治的典型應用

算法分析與設計「四」分治算法一、什麼是分治算法二、分治的典型應用

算法分析與設計「四」分治算法一、什麼是分治算法二、分治的典型應用

算法分析與設計「四」分治算法一、什麼是分治算法二、分治的典型應用
重複步驟 2 和 3，直至指針 i 和 j 相等。這樣第一趟遞歸排序就完成了，原表被分為了左右兩個子表。下面隻需遞歸操作即可。

算法分析與設計「四」分治算法一、什麼是分治算法二、分治的典型應用

算法分析與設計「四」分治算法一、什麼是分治算法二、分治的典型應用

代碼實作：

#include <iostream>
using namespace std;

void swap(int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

void QuickSort(int a[], int s, int e)
{
    if (s >= e)
        return;
    int k = a[s];     // k 為基準
    int i = s, j = e; // 左右指針
    // 下面進行一趟排序
    while (i != j)
    {
        while (j > i && a[j] >= k)
            --j;
        swap(a[i], a[j]);
        while (i < j && a[i] <= k)
            ++i;
        swap(a[i], a[j]);
    } // 此時 a[i] = k
    QuickSort(a, s, i - 1);
    QuickSort(a, i + 1, e);
}

int a[] = {2, 1, 3, 7, 12, 11, 8, 9};

int main()
{
    int size = sizeof(a) / sizeof(int);
    QuickSort(a, 0, size - 1);
    for (int i = 0; i < size; ++i)
        cout << a[i] << ' ';
    cout << endl;
    return 0;
}

注意：有個小問題，在實作 swap 交換兩個數時，剛開始用到了異或運算 a^=b; b^=a; a^=b; ，發現輸出了好多 0。這時因為 i 最終等于 j，這時兩個要交換的數相等，導緻 i ^ j = 0 。

複雜度分析：

快速排序的最壞時間複雜度是 O ( n ² ) O(n²) O(n²)，比如說順序數列的快排。但它的平均時間複雜度是 O ( n l o g n ) O(nlogn) O(nlogn)，且 O ( n l o g n ) O(nlogn) O(nlogn) 記号中隐含的常數因子很小，比複雜度穩定等于 O ( n l o g n ) O(nlogn) O(nlogn) 的歸并排序要小很多。是以，對絕大多數順序性較弱的随機數列而言，快速排序總是優于歸并排序。

應用三：輸出前 m 大的數

問題描述：給定一個數組包括 n 個元素，統計前 m 大的數并且把這 m 個數從大到小輸出。

輸入：第一行包含一個整數 n，表示數組的大小（n < 100000）。第二行包含 n個整數，表示數組的元素，整數之間以一個空格分開。每個整數的絕對值不超過100000000。第三行包含一個整數 m（m < n）。

輸出：從大到小輸出前m大的數，每個數一行。

解題思路：當然，你可以選擇先排序後再進行輸出，這時時間複雜度 O ( n l o g n ) O(nlogn) O(nlogn)。但其實我們可以選擇一種時間複雜度更小的解法：把前 m 大的都弄到數組最右邊，複雜度 O ( n ) O(n) O(n) 。然後對這最右邊 m 個元素排序再輸出，複雜度 O ( l o g n ) O(logn) O(logn) 。總的時間複雜度為 O ( n + m l o g m ) O(n+mlogm) O(n+mlogm)。當 m << n 時，這種算法時間複雜度相當于 O ( n ) O(n) O(n)，優勢就比較明顯了。

将前 m 大的都弄到數組最右邊的時間為什麼為 O ( n ) O(n) O(n) ？

算法分析與設計「四」分治算法一、什麼是分治算法二、分治的典型應用

// 輸入樣例
5
5 2 11 3 12
3
// 輸出樣例
5
11
12

代碼實作：

#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 100005

int a[MAXN];
int n, m;

void swap(int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

// 利用分治思想 ———— 先将前 m 大的數移至右邊，再對這 m 個數排序
void arrangeRight(int a[], int s, int e, int k)
{
    if (s >= e)
        return;
    if (k == e - s + 1)
        return;
    int i = s, j = e;
    int key = a[s];
    // 基準元素歸位，使得左側小于基準元素，右側大于基準元素
    while (i != j)
    {
        while (i < j && a[j] >= key)
            --j;
        swap(a[i], a[j]);
        while (i < j && a[i] <= key)
            ++i;
        swap(a[i], a[j]);
    }
    // 邊界條件及遞歸方式
    if (k == e - i + 1)
        return;
    else if (k < e - i + 1)
        arrangeRight(a, i + 1, e, k);
    else
        arrangeRight(a, s, i - 1, k - e + i - 1);
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    cin >> m;
    // 前 m 大的數弄到右邊
    arrangeRight(a, 0, n - 1, m);
    // 再對這 m 個數排序，sort 類似快排，n*log(n)。
    sort(a + n - m, a + n);
    while (m--)
        cout << a[--n] << endl;
    return 0;
}

應用四：求排列的逆序數

問題描述：

算法分析與設計「四」分治算法一、什麼是分治算法二、分治的典型應用

解題思路：

當然，你可以采取枚舉方式，對每一個元素都周遊，複雜度 O ( n 2 ) O(n^{2}) O(n2) 會逾時，是以這裡暫且不提此解法。

下面來看分治算法解決此問題，其複雜度為 O ( n l o g n ) O(nlogn) O(nlogn)

将數組分成兩半，分别求出左半邊的逆序數和右半邊的逆序數；
再算有多少逆序是由左半邊取一個數和右半邊取一個數構成的。（要求 O ( n ) O(n) O(n) 實作）

如何用 O ( n ) O(n) O(n) 時間實作第二步呢？關鍵就是：左半邊和右半邊都是排好序的。比如，都是從大到小排序的。這樣，左右半邊隻需要從頭到尾各掃一遍，就可以找出由兩邊各取一個數構成的逆序個數。

算法分析與設計「四」分治算法一、什麼是分治算法二、分治的典型應用

其實總結而言，此問題解法可以由歸并排序改進所得，隻需加上計算逆序的步驟即可。

代碼實作：

#include <iostream>
using namespace std;

int a[8] = {3, 7, 8, 10, 2, 5, 11, 12};
int b[8];      // 用于存放中間結果
int count = 0; // 記錄逆序數

// 歸并有序序列，并計算逆序數個數
void MergeAndCountNum(int a[], int s, int m, int e, int tmp[])
{
    int pb = 0;
    int p1 = s, p2 = m + 1;
    while (p1 <= m && p2 <= e)
    {
        if (a[p1] < a[p2])
            tmp[pb++] = a[p1++];
        else
        {
            tmp[pb++] = a[p2++];
            // 當出現一個逆序時，其後 m+1-p1 個數都是逆序
            count += m + 1 - p1;
        }
    }
    while (p1 <= m)
        tmp[pb++] = a[p1++];
    while (p2 <= e)
        tmp[pb++] = a[p2++];
    for (int i = 0; i < e - s + 1; ++i)
        a[s + i] = tmp[i];
}

// 利用遞歸思想
void MergeSort(int a[], int s, int e, int tmp[])
{
    if (s < e)
    {
        int m = s + (e - s) / 2;           // 中點
        MergeSort(a, s, m, tmp);           // 前段排序
        MergeSort(a, m + 1, e, tmp);       // 後段排序
        MergeAndCountNum(a, s, m, e, tmp); // 歸并同時計算逆序數
    }
}

int main()
{
    int size = sizeof(a) / sizeof(int);
    MergeSort(a, 0, size - 1, b);
    cout << count;
    return 0;
}

算法分析與設計「四」分治算法一、什麼是分治算法二、分治的典型應用

文章目錄

一、什麼是分治算法

二、分治的典型應用

應用一：歸并排序

應用二：快速排序

應用三：輸出前 m 大的數

應用四：求排列的逆序數

繼續閱讀

資料結構排序算法--快速排序（二）

Java語言實作線性查找和二分法查找Java語言實作線性查找和二分法查找 (查找算法)

POJ 2299

【8086彙編】對數組元素進行快速排序（有提示資訊并列印排序前數組和排序後數組）

時間複雜度O(n²)之冒泡排序、選擇排序法

算法-TopK相關的問題1、給定一個數組，求其最大(小)的K個元素2、給定一個數組，求其第K大的數3、給定一個數組求中位數

TopK問題的Java實作

LeetCode刷題記錄---并查集（DSU）算法⭐最長連續序列：⭐情侶牽手：

⑤算法與資料結構-java-棧

基于貪心算法的區間問題參考區間完全覆寫問題最大不相交區間數

歸并排序的時間複雜度

周鴻祎：把職業程式員進行到底

【分治算法】快速排序（c++）

找新朋友（hdu1286，歐拉函數）

[轉]九大排序算法——C語言實作及詳解

資料結構與算法（27）——排序（二）