算法

分治算法

分治，顾名思义就是分而治之，是一种很古老但很实用的策略，或者说战略。本意是将一个较大的问题拆分成许多小的问题来解决。小问题都解决了，大问题也就解决了。

在现实生活中，什么样的问题才能使用分治法解决呢，简单来说，需要满足以下3个条件：

• 原问题可分解为若干个规模较小的相同子问题。
• 子问题相互独立。
• 子问题的解可以合并为原问题的解。

比如国家人口普查，这是一个很大的问题，一下子普查完是很难的，但是可以分治为每个省市县乡来进行统计就比较合适了。再比如综艺节目海选，也是使用分治法，在每个代表城市分别进行海选，然后再选择比较优秀的选手参加比赛等等。

分治算法秘籍

分治法解题的一般步骤：

1. 分解： 将要解决的问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
2. 治理： 求解各个子问题。由于各个子问题与原问题形式相同，只是规模较小而已，而当子问题划分得足够小时，就可以用较为简单的方法解决。
3. 合并： 按原问题的要求，将子问题的解逐层合并构成原问题的解。

在分治算法中，各个子问题形式相同，解决的方法也一样，因此我们可以使用递归算法快速解决，递归是彰显分治法优势的利器。

算法应用

二分搜索

二分搜索算法是一个时间复杂度为 O(logn) 的算法，这是一种极其高效的时间复杂度。有的时候甚至比时间复杂度是常量级 O(1) 的算法还要高效。

生活例子：

小时候电视节目，有个猜价格的游戏，每个人都有3次机会，最终猜的价格越接近上品的价格，那么这个商品就是你的了。大致过程如下：

主持人：“xxx双开门冰箱，请猜价格。”

参与人：“3000元。”

主持人：“少了，请第二次猜价格。”

参与人：“2800元。”

主持人：“少了，请第三次猜价格。”

...

电视机旁边的你："天啊！怎么会有怎么笨的笨蛋？"

问题分析，如果是n个数，那么最坏的情况要猜n次，其实我们没有必要一个一个地猜，因为这些数都是有序的，它是一个二分搜索问题。我们可以使用折半查找策略，每次和中间元素比较，如果中间元素小，则在前半部分查找，如果比中间值大，则去后半部分查找。

算法设计

利用二分思想，每次都与区间的中间数据比对大小，缩小查找区间的范围，例如一个班级的考试成绩分数：8，11，19，23，27，33，45，55，67，98，需要查找19分为止，如下图：

其中，low 和 high 表示待查找区间的下标，mid 表示待查找区间的中间元素下标。

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

代码实现

/**
 * 二分搜索
 * @param nums 有序数组
 * @param target 待查找数值
 * @return
 */
private static int binarySearch(int[] nums,int target) {
    if(null == nums) return -1;
    int low = 0,high = nums.length-1;
    while (low <= high){
        int mid = low + (high - low) / 2;
        if(target == nums[mid]){
            return mid;
        }else if(target < nums[mid]){
            high = mid - 1;
        }else if(target > nums[mid]){
            low = mid + 1;
        }
    }
    return -1;
}

应用场景及局限性

⭐ 二分查找依赖的是顺序表结构，简单点说就是数组。

二分查找只能用在数据是通过顺序表来存储的数据结构上。如果你的数据是通过其他数据结构存储的，则无法应用二分查找。

⭐ 二分查找针对的是有序数据。

二分查找对这一点的要求比较苛刻，数据必须是有序的。如果数据没有序，我们需要先排序。

⭐ 数据量太小不适合二分查找

如果要处理的数据量很小，完全没有必要用二分查找，顺序遍历就足够了。比如我们在一个大小为 15 的数组中查找一个元素，不管用二分查找还是顺序遍历，查找速度都差不多。只有数据量比较大的时候，二分查找的优势才会比较明显。

⭐ 数据量太大也不适合二分查找

二分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。

归并排序

归并排序的性能不受输入数据的影响，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。

归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法设计

把长度为n的输入序列分成两个长度为n/2的子序列；

对这两个子序列分别采用归并排序；

将两个排序好的子序列合并成一个最终的排序序列。

代码实现

首先编写一个数组合并方法 merge，将分解的数组合并为一个有序数组，然后编写排序方法 mergeSort：

// 归并排序
public static int[] mergeSort(int[] nums){

    // 定义递归结束条件
    if(nums.length < 2){
        return nums;
    }

    // 分解数组
    int mid = nums.length / 2;
    int[] left = Arrays.copyOfRange(nums,0,mid);
    int[] right = Arrays.copyOfRange(nums,mid,nums.length);

    // 递归
    return merge(mergeSort(left),mergeSort(right));
}


/**
 * 将2个组合并为一个有序数组
 * @param left
 * @param right
 * @return
 */
public static int[] merge(int[] left,int[] right){
    int[] result = new int[left.length+right.length];
    for (int index = 0,i = 0,j = 0; index < result.length; index++) {
        if(i>=left.length){
            // 左数组越界，说明没有数据了，直接使用右数组赋值
            result[index]=right[j++];
        }else if(j>=right.length){
            // 右数组越界，说明没有数据了，直接使用左数组赋值
            result[index]=left[i++];
        }else if(left[i]>right[j]){
            result[index]=right[j++];
        }else{
            result[index]=left[i++];
        }
    }
    return result;
}

动图演示

总结

归并排序的处理过程是由下到上的，先处理子问题，然后再合并。

归并排序的时间复杂度任何情况下都是 O(nlogn)，看起来非常优秀。但是，归并排序并没有像快排那样，应用广泛，因为它有一个致命的“弱点”，那就是归并排序不是原地排序算法。

因为合并方法需要额外的空间存储，其空间复杂度是O(n)。

快速排序

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。

算法设计

从数列中挑出一个元素，称为 “基准”（pivot）；

重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

下图展示分区的整个过程：

代码实现

首先编写分区方法 partition，将小于基准值的元素进行排序；然后编写排序方法 quickSort 进行递归计算。

/**
 * 快速排序
 * @param arr
 * @param start
 * @param end
 * @return
 */
public static int[] quickSort(int[] arr,int start,int end){
    int si = partition(arr,start,end);
    if (si > start){
        quickSort(arr,start,si-1);
    }
    if (si < end){
        quickSort(arr,si+1,end);
    }
    return arr;
}


/**
 * 分区
 * @param arr
 * @param start
 * @param end
 * @return
 */
public static int partition(int[] arr,int start,int end){
    // 获取基准点
    int pivot = (int) (start+Math.random()*(end-start+1));

    // 将基准点放到数组最后面（交换）
    int temp = arr[pivot];
    arr[pivot] = arr[end];
    arr[end] = temp;

    // 比基准数大的索引下标，用于交换位置
    int minIndex = start - 1;

    for (int i = start; i <= end; i++) {
        // 依次对 i 元素，与基准数对比
        if(arr[i] <= arr[end]){
            minIndex++;
            if(i>minIndex){
                int tmp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = tmp;
            }
        }
    }
    return minIndex;
}

动图演示

总结

快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。

作者： Zealon
崇尚简单，一切简单自然的事物都是美好的。