分治算法解析與實戰【九大經典例子（附完整代碼）】（上篇）

學習網站推薦：前些天發現了一個巨牛的人工智能學習網站，通俗易懂，風趣幽默，忍不住分享一下給大家。​​點選跳轉到網站​​

【分治算法】<上篇>

一、算法思想簡介

1.基本思想：”分而治之“，将一個複雜問題分解成兩個或多個相同或相似的子問題，再把子問題分解成更小的子問題…直到最後子問題可以簡單的直接求解，原問題的解即為所有子問題的解的合并。

2.經典例子：

• 漢諾塔
• 二分查找（遞歸版）
• 歸并排序（遞歸版）
• 快速排序（遞歸版）

二、經典例子的代碼實作

1.漢諾塔：

• 目标：将所有盤子從A柱移動到C柱，同一根柱子在任何時候不允許出現上面的某個盤子大于下面的某個盤子的情況。
• 基本思想（圖解）：将A柱的n個盤子全部移動到C柱，可先将A柱的前n-1個盤子移動到B柱子，再将第n個盤子移到C柱，再将B柱的n-1個盤子移到C柱。
• 代碼實作

public class Hanoitower {

    public static void main(String[] args) {
        hanoiTower(3, 'A', 'B', 'C');
    }

    private static void hanoiTower(int num, char a, char b, char c) {
        //如果隻有一個盤子
        if (num == 1) {
            System.out.println("第1個盤子從" + a + "->" + c);
        } else { //如果有n>=2個，可抽象成兩個盤，一個是最下面的一個盤，另一個是上面的所有盤
            //将上面的盤從A->B
            hanoiTower(num - 1, a, c, b);
            //移動最下面的盤從A->C
            System.out.println("第" + num + "個盤從" + a + "->" + c);
            //将上面的盤從B->C
            hanoiTower(num - 1, b, a, c);
        }
    }

}      

2.二分查找（遞歸版）：

• 目标：在有序表查找某值是否存在。
• 基本思想（圖解）：



• 代碼實作：

public class BinarySearch {

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5};
        System.out.println(search(a, 1));
        System.out.println(search(a, 3));
        System.out.println(search(a, 5));
        System.out.println(search(a, 9));
    }

    public static boolean search(int[] a, int key) {
        return inSearch(a, 0, a.length - 1, key);
    }

    private static boolean inSearch(int[] a, int low, int high, int key) {
        int mid;
        while (low <= high) {
            mid = (low + high) / 2;
            if (key == a[mid]) {
                return true;
            } else if (key < a[mid]) {
                return inSearch(a, 0, mid - 1, key);
            } else {
                return inSearch(a, mid + 1, high, key);
            }
        }
        return false;
    }

}      

3.歸并排序（遞歸版）：

• 目标：使序列有序。
• 基本思想（圖解）：初始序列含有n個元素，則可看成是n個有序子序列，每個子序列的長度為1，然後兩兩歸并，得到Math.ceil(n/2)個長度為2或1的有序子序列；再兩兩歸并，…，如此重複，直到得到一個長度為n的有序序列位置。
• 代碼實作：

public class MergeSort {

    public static void sort(int[] a) {
        int n = a.length - 1;
        MSort(a, a, 1, n);
    }

    //将SR[s..n]歸并為有序的TR1[s..n]
    private static void MSort(int[] SR, int[] TR1, int s, int n) {
        int m;
        int[] TR2 = new int[n + 1]; // SR, TR1, TR2等長
        if (s == n) {
            TR1[s] = SR[s];
        } else {
            m = (s + n) / 2; // 将SR[s..n]平均分為SR[s..m]和SR[m+1..n]
            MSort(SR, TR2, s, m); // 遞歸将SR[s..m]歸并為有序的TR2[s..m]
            MSort(SR, TR2, m + 1, n); // 遞歸将SR[m+1..n]歸并為有序的TR2[m+1..n]
            Merge(TR2, TR1, s, m, n); // 将TR2[s..m]和TR2[m+1..n]歸并到TR1[s..n]
        }
    }

    // 将有序的SR[s..m]和SR[m+1..n]歸并為有序的TR[i..n]
    private static void Merge(int[] SR, int[] TR, int s, int m, int n) {
        int j, k, l; // k為左塊的起始下标，j為右塊的起始下标
        for (k = s, j = m + 1; s <= m && j <= n; k++) { //SR中記錄由小到大歸并入TR
            if (SR[s] < SR[j]) {
                TR[k] = SR[s++];
            } else {
                TR[k] = SR[j++];
            }
        }
        if (s <= m) {
            for (l = 0; l <= m - s; l++) {
                TR[k + l] = SR[s + l]; // 将剩餘的SR[s..m]複制到TR
            }
        }
        if (j <= n) {
            for (l = 0; l <= n - j; l++) {
                TR[k + l] = SR[j + l]; // 将剩餘的SR[j..m]複制到TR
            }
        }
    }

}      

• 目标：使序列有序。
• 基本思想：通過一趟排序将待排序記錄分割成獨立的兩部分，其中每一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可以分别對着兩部分記錄繼續進行排序，以達到整個序列有序的目的。
• 代碼實作：

public class QuickSort {

    public static void sort(int[] a) {
        int n = a.length - 1;
        QSort(a, 1, n);
    }

    private static void QSort(int[] a, int low, int high) {
        int pivot; // 樞軸的下标，将某個數放在此位置，使得它左邊的值都比它小，右邊的都比它大
        if (low < high) {
            pivot = Partition(a, low, high); // 将a[low..high]一分為二，算出樞軸下标pivot
            QSort(a, low, pivot - 1); // 對低子表遞歸排序
            QSort(a, pivot + 1, high); // 對高子表遞歸排序
        }
    }

    // 交換順序表a中子表的記錄，使樞軸記錄到為，并傳回其位置
    private static int Partition(int[] a, int low, int high) {
        int pivotkey = a[low]; // 用子表的第一個記錄作樞軸記錄
        while (low < high) { // 從表的兩端交替向中間掃描
            while (low < high && a[high] >= pivotkey) {
                high--;
            }
            swap(a, low, high); // 将比樞軸值小的記錄交換到低端
            while (low < high && a[low] <= pivotkey) {
                low++;
            }
            swap(a, low, high); // 将比樞軸值大的記錄交換到高端
        }
        return low; // 最終low == high，所有傳回樞軸所在位置
    }

    private static void swap(int[] a, int x, int y) {
        int temp;
        temp = a[x];
        a[x] = a[y];
        a[y] = temp;
    }

}