算法-归并排序

整体架构流程

归并算法采用分治法：将问题分解为几个规模较小但类型于原问题的子问题，递归求解这些子问题，然后再合并这些子问题的解来建立原来问题的解。
分解 分解待排序的n个元素的序列成各具有n/2个元素的两个子序列。直至子序列为1个元素。
解决 使用归并排序递归的排序两个子序列。
合并 合并两个已排序的子序列以产生已排序的答案。

技术细节

采用排序时，每次创建两个子序列

import java.util.Arrays;

public class MergeManyArray {
    public static void main(String... args) {
        int[] arr = {5, 2, 9, 1, 3, 6};
        sort(arr);
    }

    private static void sort(int[] arr) {
        System.out.println("排序前数组：" + Arrays.toString(arr));
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("排序后数组：" + Arrays.toString(arr));
    }

    private static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        //计算中间数
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        System.out.println("排序参数：left = " + left + " mid = " + mid + " right=" + right);
        //左边数组长度
        int leftLength = mid - left + 1;
        //右边数组长度
        int rightLength = right - mid;
        System.out.println("排序参数：leftLength = " + leftLength + " rightLength = " + rightLength);
        //创建两个数组
        int[] leftArray = new int[leftLength];
        int[] rightArray = new int[rightLength];
        //向两个数组复制数据
        for (int i = 0; i < leftLength; i++) {
            leftArray[i] = arr[left + i];
        }
        for (int i = 0; i < rightLength; i++) {
            rightArray[i] = arr[mid + i + 1];
        }
        System.out.println("左边数据：" + Arrays.toString(leftArray));
        System.out.println("右边数据：" + Arrays.toString(rightArray));

        //设置左，右两个数组的索引
        int leftIndex = 0, rightIndex = 0;

        //升序排序
        //因排序的两个数组，每个数组元素是有序的
        //所以耽搁数组无需排序
        for (int k = left; k <= right; k++) {
            if (rightIndex >= rightLength) {
                //右边数组，已全部比较完成。
                arr[k] = leftArray[leftIndex];
                leftIndex++;
            } else if (leftIndex >= leftLength) {
                //左边数组，已全部比较完成。
                arr[k] = rightArray[rightIndex];
                rightIndex++;
            } else if (leftArray[leftIndex] <= rightArray[rightIndex]) {
                arr[k] = leftArray[leftIndex];
                leftIndex++;
            } else {
                arr[k] = rightArray[rightIndex];
                rightIndex++;
            }
        }
        System.out.println("合并排序：" + Arrays.toString(arr));
    }
}

采用排序时，采用一个数组

复用一个数组，数组长度等于当前数组长度

import java.util.Arrays;

public class MergeOneArray {
    public static void main(String... args) {
        int[] arr = {5, 2, 9, 1, 3, 6};
        sort(arr);
    }

    /**
     * 排序
     * @param arr 数组
     */
    private static void sort(int[] arr) {
        System.out.println("排序前数组：" + Arrays.toString(arr));
        int[] copy = new int[arr.length];
        mergeSort(arr, copy, 0, arr.length - 1);
        System.out.println("排序后数组：" + Arrays.toString(arr));
    }

    /**
     * 归并排序
     * @param arr 数组
     * @param copy 复制数组
     * @param left 左边索引位置
     * @param right 右边索引位置
     */
    private static void mergeSort(int[] arr, int[] copy, int left, int right) {
        if (left >= right) {
            return;
        }
        //计算中间数
        int mid = (left + right) / 2;
        mergeSort(arr, copy, left, mid);
        mergeSort(arr, copy, mid + 1, right);
        merge(arr, copy, left, mid, right);
    }

    /**
     * 排序
     * @param arr 数组
     * @param copy 复制数组
     * @param left 左边索引
     * @param mid  中间索引
     * @param right 右边索引
     */
    private static void merge(int[] arr, int[] copy, int left, int mid, int right) {
        System.out.println("排序参数：left = " + left + " mid = " + mid + " right=" + right);

        //复制数据
        for (int i = left; i <= right; i++) {
            copy[i] = arr[i];
        }
        System.out.println("复制数组：" + Arrays.toString(copy));


        //设置左，右两个数组的索引
        int leftIndex = left, rightIndex = mid + 1;

        //升序排序
        //需要比较的mid左右两边的元素是有序的
        //所以数组无需排序
        for (int k = left; k <= right; k++) {
            if (rightIndex >= right+1) {
                //右边数组，已全部比较完成。
                arr[k] = copy[leftIndex];
                leftIndex++;
            } else if (leftIndex >= mid+1) {
                //左边数组，已全部比较完成。
                arr[k] = copy[rightIndex];
                rightIndex++;
            } else if (copy[leftIndex] <= copy[rightIndex]) {
                arr[k] = copy[leftIndex];
                leftIndex++;
            } else {
                arr[k] = copy[rightIndex];
                rightIndex++;
            }
        }
        System.out.println("合并排序：" + Arrays.toString(arr));
        //为了打印更好理解，实际算法中不需要
        for (int i = left; i <= right; i++) {
            copy[i] = 0;
        }
    }
}

小结

采用单个数组，可以减少数组的创建，以提供算法性能