分治

浅谈分治算法

使用场景

可以分解为若干 MECE 的相同子问题，即具有最优子结构

步骤

1. 分解
2. 求解：直接/递归
3. 合并

案例

二分查找(基本)

• 算法流程：
  • 选择一个标志位 i 将集合分为两个子集合
  • 判断 arr[i] 和 target 关系，相等则返回
  • 否则判断在左侧还是右侧查找
  • 递归直到找到或退出
• 代码： 二分查找

全排列问题

• 问题描述：
  • 有1，2，3，4个数，问你有多少种排列方法，并输出排列。
• 问题分析：
  • 确定第一位后，对后续序列进行全排列。直到只有一个数字时停止。
• 代码：

public class Test{
    public static void main(String[] args){
        int[] arr = {1, 2, 3, 4};
        fullSort(arr, 0, arr.length - 1);
    }

    public static void fullSort(int[] arr, int start, int end){
        // 递归终止条件
        if (start == end){
            for (int i : arr){
                System.out.print(i);
            }
            System.out.prinln();
            return;
        }
        for (int i = start; i <= end; i++){
            swap(arr, i, start);
            fullSort(arr, start + 1, end); // 把该位放到开头，对剩下的位数全排列
            swap(arr, i, start;)
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

归并排序

• 问题分析：
  • 一个序列从中点分为两个有序子序列，然后合并。
• 代码：

import java.util.Arrays;

public class guibing {
     static int[] mergeSort(int[] sourceArray){
        if (sourceArray.length <= 1) return sourceArray;
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        int mid = arr.length >> 1;

        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);

        return merge(mergeSort(left), mergeSort(right));
    }

    // a1 & a2 are both sorted
    static int[] merge(int[] a1, int[] a2){
        int[] result = new int[a1.length + a2.length];
        int sortedIndex = 0;
        int i = 0, j = 0;

        while(i < a1.length && j < a2.length){
            if (a1[i] <= a2[j]){
                result[sortedIndex++] = a1[i++];
            } else {
                result[sortedIndex++] = a2[j++];
            }
        }
        while(i < a1.length){
            result[sortedIndex++] = a1[i++];
        }
        while(j < a2.length){
            result[sortedIndex++] = a2[j++];
        }
        return result;
    }


    public static void main(String[] args){
        int[] arr = {3,76,4,32,643,2,2,3,4,5,6};
        System.out.println(Arrays.toString(mergeSort(arr)));
    }
}

快速排序

• 问题分析：
  • partition: 一个序列，选定一个 pivot ，调整 pivot 位置使得它左边的值小于它，右边的值大于它，并确定该 pivot 的位置
  • 对于左右的序列分别进行快速排序
• 代码：

import java.util.Arrays;
public class kuaipai {

    static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    static int[] quickSort(int[] sourceArray) {
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        return quickSortRecursion(arr, 0, arr.length - 1);
    }

    static int[] quickSortRecursion(int[] arr, int left, int right) {
        if (left < right) {
            int mid = partition(arr, left, right);
            quickSortRecursion(arr, left, mid - 1);
            quickSortRecursion(arr, mid + 1, right);
        }
        return arr;
    }

    static int partition(int[] arr, int left, int right) {
        int pivot = left;
        int index = pivot + 1;
        int i = index;

        while (i <= right) {
            if (arr[i] <= arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
            i++;
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }

    public static void main(String[] args) {
        int[] arr = { 3, 76, 4, 32, 643, 2, 2, 3, 4, 5, 6 };
        System.out.println(Arrays.toString(quickSort(arr)));
    }
}

汉诺塔

• 问题分析：
  • 原问题：n 个盘子，从 source 到 target ，中途可借助 temp
  • 子问题：上面 n-1 个盘子放到temp，最底下盘子到target，然后 temp 上的 n-1 个盘子借助 source 移到 target 上。 如果 n = 1， 直接移。
• 代码：

public static void hanoi(int n, String source, String temp, String target){
    if (n == 1){
        move (n, source, target);
    } else {
        hanoi (n - 1, source, target, temp);
        move (n, source, target);
        hanoi (n - 1, temp, source, target);
    }
}
private static void move(int n, String source, String target){
    System.out.printf("第 %d 号盘子 move: %s ---> %s \n", n, source, target);
}