算法05-减治法

一、介绍

减治法是每一步都能缩小一定的问题规模（-1，-k，-n/2等），最后变成1个最小的小问题。

减治法常见应用：堆排序、深度优先查找。

二、堆排序

1、基本思想

堆排序:基于完全二叉树的升序排序。

堆排序的过程：

将线性结构(比如数组)当作完全二叉树来排序：如果数组中一个元素A的下标为k，那么下标为(k-1)/2的元素相当于A的父节点，下标为2k+1的元素相当于A的左子节点，下标为2k+2的元素相当于A的右子节点；
对n个元素进行排序，将最小值放到数组的首位：先把节点k的左子树的最小值放到k的左子节点，再把先把节点k的右子树的最小值放到k的右子节点，然后节点k与其左右子节点的最小值即为数组的最小值。这里需要使用递归。
取出数组的最小值，放入数组M；
令n=n-1，重复步骤2、3，直到n=0,排序完成：M即为拍好序的数组。

应用：当数据源为无序或链式结构的时候，进行二分查找。一般不用于排序，空间复杂度太高。

2、代码实现

public static <E extends Comparable<E>> E[] heapSort(E[] arr) {
    if (Tool.isEmpty(arr)) {
        return null;
    }

    //由于直接new泛型数组报错，所以使用Arrays.copyOf()
    E[] result = Arrays.copyOf(arr, arr.length);
    //缩小问题规模：每次-1
    for (int i = 0; i < arr.length; i++) {
        // 缩小后的问题规模
        int n = arr.length - i;
        // 解决小问题：对首位进行单次堆排序，将最小值放到首位
        heapSort(arr, n, 0);
        // 获取最小值
        result[i] = arr[0];
        // 将未排序的数据放到首位
        arr[0] = arr[n - 1];
    }

    return result;
}

/**
 * 单次堆排序：递归设置当前节点与其左右节点的最小值
 * @param arr：要排序的数组
 * @param n：表示数组大小，即问题的规模
 * @param k：要比较的节点下标
 */
public static <E extends Comparable<E>> void heapSort(E[] arr, int n, int k) {
    // 左节点下标
    int left = 2 * k + 1;
    // 右节点下标
    int right = 2 * k + 2;
    if (left >= n) {
        return;
    }

    // 将左子树中最小值放到左节点
    heapSort(arr, n, left);
    // 再将右子树中最小值放到右节点
    heapSort(arr, n, right);

    E data = arr[k];
    E l = arr[left];
    //右节点如果不存在，就将它的值设为MAX
    E r = right < n ? arr[right] : null;
    //如果当前节点是最小的，直接返回
    if (data.compareTo(l) <= 0 && (r == null || data.compareTo(r) <= 0)) {
        return;
    }
    //如果左节点是最小的，就将左节点与当前节点交换
    if (r == null || l.compareTo(r) < 0) {
        arr[left] = data;
        arr[k] = l;
        //如果右节点是最小的，就将右节点与当前节点交换
    } else {
        arr[right] = data;
        arr[k] = r;
    }
}

三、深度优先查找

1、基本思想

深度优先查找是优先按纵深查找的思想，按照一个方向一直走，没有了路就回退，然后换方向找，知道找到终点。

操作步骤：

用一个二维数组模拟迷宫，数组的值：0表示走得通，1表示走不通，2表示走过，3表示墙。并指定起点和终点；
从起点开始，按左下右上的顺序查找，如果能走到下一个点，就将它的值标记为2，然后以这个点为新的起点开始，按左下右上的顺序查找；如果不能走到下一个点，就将它的值标记为1，然后回退到上一个点，从剩下的方向查找；
重复步骤2，知道走到终点。

应用：迷宫找路

2、代码实现

/**
 * @param arr    需要查找的数组。其中0表示走得通，1表示走不通，2表示走过，3表示墙。
 * @param startX 起点横坐标
 * @param startY 起点纵坐标
 * @param endX   终点横坐标
 * @param endY   终点纵坐标
 */
public static boolean dfsSort(int[][] arr, int startX, int startY, int endX, int endY) {
    if (startX < 0 || startY < 0 || endX < 0 || endY < 0) {
        return false;
    }
    // 到达终点
    if (arr[endX][endY] == 2) {
        return true;
    }

    //如果没有走过，就按左下右上的顺序查找
    if (arr[startX][startY] == 0) {
        //标记已走过
        arr[startX][startY] = 2;
        //从左边开始找
        if (dfsSort(arr, startX - 1, startY, endX, endY)) {
            return true;
            //从上边开始找
        } else if (dfsSort(arr, startX, startY - 1, endX, endY)) {
            return true;
            //从右边开始找
        } else if (dfsSort(arr, startX + 1, startY, endX, endY)) {
            return true;
            //从下边开始找
        } else if (dfsSort(arr, startX, startY + 1, endX, endY)) {
            return true;
            //如果没有路，就标记为1，然后返回
        } else {
            arr[startX][startY] = 1;
            return false;
        }
    }
    return false;
}