分治算法

将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同，求出子问题的解，就可得到原问题的解

应用场景

原问题可以分解为多个子问题
原问题在分解过程中，递归地求解子问题
在求解并得到各个子问题的解后，应能够采用某种方式、方法合并或构造出原问题的解

框架

分解，将要解决的问题划分成若干规模较小的同类问题
求解，当子问题划分得足够小时，用较简单的方法解决
合并，按原问题的要求，将子问题的解逐层合并构成原问题的解

实例

快速排序

public class QuickSort {

    private InsertSort insertSort = new InsertSort();

    public void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private void quickSort(int[] arr, int left, int right) {
//        if (left >= right)
//           return ;

        if (right - left <= 15) {
            insertSort.sortOp(arr);
            return;
        }

        int p = partition(arr, left, right);
        quickSort(arr, left, p);
        quickSort(arr, p + 1, right);
    }

//    private int partition(int[] arr, int left, int right) {
//        int v = arr[left];
//        int i = left + 1;
//        int j = left;
//        while (i <= right && j < right) {
//            if (arr[i] <= v) {
//                if (i != j) {
//                    ArrayUtils.swap(arr, i, j + 1);
//                }
//                j++;
//            }
//            i++;
//        }
//        ArrayUtils.swap(arr, left, j);
//        System.out.println(j);
//        return j;
//    }

    private int partition(int[] arr, int left, int right) {
        int v = arr[left];
        int j = left;
        for (int i = left + 1; i <= right; i++) {
            if (arr[i] < v) {
                ArrayUtils.swap(arr, i, j + 1);
                j++;
            }
        }
        ArrayUtils.swap(arr, left, j);
        System.out.println(j);
        return j;
    }
}

归并排序

public class MergeSort {

    // [left, right]
    public void sort(int[] arr, int left, int right) {
        if (right <= left) {
            return;
        }

        int middle = (left + right) / 2;
        sort(arr, left, middle);
        sort(arr, middle + 1, right);
        merge(arr, left, middle, right);
    }

    private void merge(int[] arr, int left, int middle, int right) {
        int[] temp = new int[right - left + 1];
        int i = left;
        int j = middle + 1;
        int k = 0;
        while (i <= middle && j <= right) {
            if (arr[i] < arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        while (i <= middle) {
            temp[k++] = arr[i++];
        }

        while (j <= right) {
            temp[k++] = arr[j++];
        }

        k = 0;
        while (left <= right) {
            arr[left++] = temp[k++];
        }
        ArrayUtils.printArray(arr);
    }
}