分治算法

/ 计算机基础 / 441浏览

分治算法

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

在现实生活中,什么样的问题才能使用分治法解决呢,简单来说,需要满足以下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;
}

动图演示

总结

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