算法之美：分治法

在计算机科学中，分治法是一种很重要的算法。字面上理解就是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……

适用情况

1. 该问题的规模缩小到一定的程度就可以容易地解决
2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3. 利用该问题分解出的子问题的解可以合并为该问题的解；
4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

分治法的复杂性分析

一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：

T（n）= k T(n/m)+f(n)

通过迭代法求得方程的解：

递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。
通常假定T(n)是单调上升的，从而当 mi≤n<mi+1时，T(mi)≤T(n)<T(mi+1)。

分治法-归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

归并排序动态演示

我们来推倒下归并排序的时间和空间复杂度，归并排序的比较是分层次来归并的（第一次是两两归并，之后再在第一次归并的基础上两两归并，每一层归并的次数为上一层除二，最终形成一二叉树，该二叉树的高即为归并次数logn，而每一层的比较次数恒等于n，所以时间复杂度求得nlogn）。

归并的空间复杂度就是由临时的数组和递归时压入栈的数据占用的空间：n + logn；所以空间复杂度为: O(n)

时间复杂度：O(nlogn)
空间复杂度：O(n)

代码实现

public class MergeSort {
    public static void merge(int[] arr, int low, int mid, int high, int[] tmp) {
        int i = 0;
        //左边序列和右边序列起始索引
        int j = low, k = mid + 1;
        while (j <= mid && k <= high) {
            if (arr[j] <= arr[k]) {
                tmp[i++] = arr[j++];
            } else {
                tmp[i++] = arr[k++];
            }
        }
        //若左边序列还有剩余，则将其全部拷贝进tmp[]中
        while (j <= mid) {
            tmp[i++] = arr[j++];
        }

        while (k <= high) {
            tmp[i++] = arr[k++];
        }

        for (int t = 0; t < i; t++) {
            arr[low + t] = tmp[t];
        }
    }

    public static void mergeSort(int[] arr, int low, int high, int[] tmp) {
        if (low < high) {
            int mid = (low + high) / 2;
            //对左边序列进行归并排序
            mergeSort(arr, low, mid, tmp);
            //对右边序列进行归并排序
            mergeSort(arr, mid + 1, high, tmp);
            //合并两个有序序列
            merge(arr, low, mid, high, tmp);
        }
    }

    public static void main(String[] args) {
        int[] arr = {11, 44, 23, 67, 88, 65, 34, 48, 9, 12};
        int[] tmp = new int[arr.length];
        //新建一个临时数组存放
        mergeSort(arr, 0, arr.length - 1, tmp);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

}

运行结果

Connected to the target VM, address: '127.0.0.1:55067', transport: 'socket'
9 11 12 23 34 44 48 65 67 88 
Disconnected from the target VM, address: '127.0.0.1:55067', transport: 'socket'

Process finished with exit code 0

分治法-快速排序

快速排序是排序算法中效率相对较高的，但使用的人却是比较少，大家一般信手拈来的排序算法就是冒泡排序。因为冒泡排序主观，容易理解，而快速排序使用到了递归，大家可能就有点不知所措了，接下来要讲的就是快排

快速排序又称分划交换排序，其设计方法与合并排序不同。其分解方法是：在待排序的序列中选择一个元素作为分划元素，称之为主元。在经过一趟特殊分划规则处理后，分划元素左侧元素都不大于主元，右侧元素都不小于主元，此过程被称为一次分划操作。一次划分后，原序列被划分为两个待排序的子序列，在将两个子序列排序后合并成一个序列，则其为排序完成的序列。

快速排序算法中，使用分划操作将一个问题分解为两个独立的子问题。
当子序列为空或有一个元素时，被认为自问题足够小。因为空序列或者只有一个元素的子序列不需要进行任何处理自然是有序的，所以能够被认为足够小。
而快速排序算法在子问题足够小时，根据算法本身的主元的性质，在左侧的自然是小的，在右侧的自然是大的，所以快速排序在合并时很容易。只需要将原有的子序列按分治的顺序合并即可。

快速排序动态演示

• 我们来推倒下归并排序的时间和空间复杂度
• 快速排序的时间性能取决于快速排序递归的深度；那么

1. 在最差情况下，划分由 n 个元素构成的数组需要进行 n 次比较和 n 次移动。因此划分所需时间为 O(n) 。最差情况下，每次主元会将数组划分为一个大的子数组和一个空数组。这个大的子数组的规模是在上次划分的子数组的规模减 1 ，即退化到了冒泡排序(每一次都排好一个元素的顺序)，该算法需要 (n-1)+(n-2)+…+2+1= O(n^2) 时间。
2. 在最佳情况下，每次主元将数组划分为规模大致相等的两部分。设 T(n) 表示使用快速排序算法对包含 n 个元素的数组排序所需的时间，因此，和归并排序的分析相似，快速排序的 T(n)= O(nlogn)。
3. 每次递归传参left，和right，平均递归次数是log(n)次，所以平均空间复杂度是O(log(n))。在最坏情况下(数组是有序的)，则为O(n)。

时间复杂度：O( nlogn )
空间复杂度：O( logn )

代码实现

public class QuickSort {
    /**
     * 交换函数，i，j为数组索引
     */
    static void swap(int A[], int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

    /**
     * 选取一个关键字(key)作为枢轴，一般取整组记录的第一个数/最后一个，这里采用选取序列最后一个数为枢轴。
     * 设置两个变量left = 0;right = N - 1;
     * 从left一直向后走，直到找到一个大于key的值，right从后至前，直至找到一个小于key的值，然后交换这两个数。
     * 重复第三步，一直往后找，直到left和right相遇，这时将key放置left的位置即可。
     *
     * @return
     */
    static int PartSort(int[] array, int left, int right) {
        //定义基准
        int key = array[right];
        //保存rigth值
        int count = right;
        //防止数组越界
        while (left < right) {
            while (left < right && array[left] <= key) {
                ++left;
            }
            while (left < right && array[right] >= key) {
                --right;
            }
            swap(array, left, right);
        }
        swap(array, right, count);
        return right;
    }

    /**
     * 分治思想，递归调用
     */
    static void QuickSort(int array[], int left, int right) {
        //表示已经完成一个组
        if (left >= right) {
            return;
        }
        //枢轴的位置
        int index = PartSort(array, left, right);
        QuickSort(array, left, index - 1);
        QuickSort(array, index + 1, right);
    }

    public static void main(String[] args) {
        int a[] = {1, 3, -7, 54, 15, 97, 21, 11};
        QuickSort(a, 0, 7);
        for (int i = 0; i < a.length; i++) {
            System.out.print(" " + a[i]);
        }
        System.out.print("\n");
    }
}

运行结果

Connected to the target VM, address: '127.0.0.1:51776', transport: 'socket'
 -7 1 3 11 15 21 54 97
Disconnected from the target VM, address: '127.0.0.1:51776', transport: 'socket'

Process finished with exit code 0