算法03-分治法

一、定义

分治法可以通俗的解释为：把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。

分治法的精髓：

• 分--将问题分解为规模更小的子问题；
• 治--将这些规模更小的子问题逐个击破；
• 合--将已解决的子问题合并，最终得出“母”问题的解；

分治法的应用：二分查找、快速排序、归并排序、循环赛日程表等。

二、二分查找

1、基本思想

分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

查找过程：

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

2、代码实现

/**
 * @param arr   被查找的数组
 * @param start 查找开始的位置
 * @param end   查找结束的位置(不包含)
 * @param data  要查找的数据
 * @return 查找数据在数组中的下标
 */
public static <E extends Comparable<E>> int binarySearch(E[] arr, int start, int end, E data) {
    if (Tool.isEmpty(arr)) {
        return -1;
    }
    int low = start;
    // 包左不包右
    int high = end - 1;

    while (low < high) {
        int mid = (low + high) >>> 1;
        if (arr[mid].compareTo(data) == 0) {
            return mid;
        } else if (arr[mid].compareTo(data) > 0) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -low;// 返回最后查找的位置
}

三、快速排序

1、基本思想

快速排序（Quicksort）是对冒泡排序的一种改进。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序:适用于数据量大的顺序表
为什么不适合链式表？

1. 快速排序的过程，主要是查找比较数据，修改少；
2. 快速排序是从两端查找比较，如果是单链表，性能会更差。

2、代码实现

/**
 * @param arr：需要排序的数组
 * @param start:开始排序的位置
 * @param end:结束排序的位置(包含)
 */
public static <E extends Comparable<E>> void quicksort(E[] arr, int start, int end) {
    if (Tool.isEmpty(arr) || start >= end) {
        return;
    }

    int low = start;
    int high = end;
    //基准值
    E data = arr[start];
    //从两端开始，与基准值比较，小于基准值就放在左边，大于基准值就放在右边
    while (low < high) {
        //先找比基准值小的数据
        while (low < high && data.compareTo(arr[high]) <= 0) {
            high--;
        }
        //将小的数据放到左边
        arr[low] = arr[high];
        //再找比基准值小的数据
        while (low < high && data.compareTo(arr[low]) >= 0) {
            low++;
        }
        //将大的数据放到右边
        arr[high] = arr[low];
    }
    //low即为基准值的下标
    arr[low] = data;
    //对左边的数据进行快速排序
    quicksort(arr, start, low - 1);
    //对右边的数据进行快速排序
    quicksort(arr, low + 1, end);
}

四、归并排序

1、基本思想

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并过程为：比较a[i]和b[j]的大小，若a[i]≤b[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素b[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。

归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

归并排序适用于数据量大的链表,占用内存比快速排序大。

2、代码实现

/**
 * @param arr：需要排序的数组
 * @param start:开始排序的位置
 * @param end:结束排序的位置(包含)
 */
public static <E extends Comparable<E>> void megreSort(E[] arr, int start, int end) {
    if (arr == null || arr.length == 0) {
        return;
    }

    if (start >= end) {
        return;
    }
    //二进制右移，相当于除以2
    int mid = (start + end) >>> 1;
    //先把左边排好序
    megreSort(arr, start, mid);
    //再把右边排好序
    megreSort(arr, mid + 1, end);

    //创建一个临时数组，用于拷贝数据
    E[] copy = Arrays.copyOf(arr, arr.length);
    int i = start;
    int j = mid + 1;
    //把左右两边合在一起：左边的数可能大于右边
    for (int k = start; k <= end; k++) {
        //将小的数据放到arr中
        if (i <= mid && copy[i].compareTo(copy[j]) < 0) {
            arr[k] = copy[i];
            i++;
            //左边的表中数据放完后，就直接放右表数据
        } else if (i > mid && copy[i].compareTo(copy[j]) < 0) {
            arr[k] = copy[j];
            j++;
        } else if (j <= end && copy[i].compareTo(copy[j]) >= 0) {
            arr[k] = copy[j];
            j++;
            //右边的表中数据放完后，就直接放左表数据
        } else if (j > end && copy[i].compareTo(copy[j]) >= 0) {
            arr[k] = copy[i];
            i++;
        }
    }
}

五、循环赛日程表

1、介绍

循环赛日程表问题是指，设有n=2＾k个选手参加比赛，要求设计一个满足一下要求的比赛日程表:

1. 每个选手必须与其他的n-1个选手个比赛一次；
2. 每个选手每天只能赛一次 。

解决思路：

1. 先将选手两两分组，直到每组只有两名选手；
2. 然后对每组的两名选手安排赛程，先创建一个二维数组A，然后把二名选手按序号放到A的第一行，然后把1号选手复制到A的右下角，把2号选手复制到A的左下角，现在A的排序就是这两名选手的日程表；
3. 然后把上面的分组再两两合并一次，那么新的分组由之前的两个小分组组成，将这两个小分组当成2个单位，参照步骤2对他们排序，排序结果就是它们的日程表；
4. 重复步骤2和3，知道全部排好序。

2、代码实现

/**
 * @param k 选手个数的2次幂
 * @return 日程表
 */
public static int[][] cyclingRace(int k) {
    // 选手个数
    int n = 1 << k;
    //日程表
    int[][] result = new int[n][n];
    // 初始化日程表
    for (int j = 0; j < n; ) {
        result[0][j] = ++j;
    }

    //先两两分组，排好序后，再两两合并，继续排序
    for (int i = 0; i < k; i++) {
        int len = 1 << i;
        for (int j = 0; j < n; j += len * 2) {
            // 将二维数组左上部分复制到右下部分
            copyArr(result, 0, j, len, j + len, len);
            // 将二维数组右上部分复制到左下部分
            copyArr(result, 0, j + len, len, j, len);
        }
    }
    return result;
}

/**
 * 拷贝二维数组
 *
 * @param arr：被拷贝的二维数组
 * @param a1：二维数组左上角的横坐标
 * @param a2：二维数组左上角的纵坐标
 * @param b1：二维数组右下起点的横坐标
 * @param b2：二维数组右下起点的纵坐标
 * @param len:拷贝的长度
 */
public static void copyArr(int[][] arr, int a1, int a2, int b1, int b2, int len) {
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            arr[b1 + i][b2 + j] = arr[a1 + i][a2 + j];
        }
    }
}

最后

代码地址：https://gitee.com/yanhuo2008/Common/blob/master/Tool/src/main/java/gsw/tool/arithmetic/DivideConquer.java

数据结构与算法专题：https://www.jianshu.com/nb/25128590

喜欢请点赞，谢谢！