归并排序

https://www.cnblogs.com/chengxiao/p/6194356.html

 public class Main {
    /**
     * 测试入口
     *
     * @param args 参数
     */
    public static void main(String[] args) {
        int[] array = {9, 8, 7, 6, 7, 4, 10, 3, 3};
        int[] temp = new int[array.length];
        mergeSort(array, 0, array.length - 1, temp);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 归并排序
     *
     * @param array 待排序数组
     * @param left  待排序数组的需要排序的左边部分的位置
     * @param right 待排序数组的需要排序的右边部分的位置
     * @param temp  临时存储结果的数组
     */
    private static void mergeSort(int[] array, int left, int right, int[] temp) {
        //左边小于右边，那么说明还没有排好序，如果left=right,那么说明只有一个数，已经排好序
        if (left < right) {
            int middle = (left + right) / 2;
            //排序左边的数组数据（分）
            mergeSort(array, left, middle, temp);
            //排序右边的数组数据（分）
            mergeSort(array, middle + 1, right, temp);
            //将左边和右边已经排好序的数据合并在一起（合）
            merge(array, left, middle, right, temp);
        }
    }

    /**
     * 合并
     *
     * @param array  原本的数组
     * @param left   左边的位置
     * @param middle 中间的位置
     * @param right  右边的位置
     * @param temp   临时存储的数组
     */
    private static void merge(int[] array, int left, int middle, int right, int[] temp) {
        //左边数据的位置
        int leftIndex = left;
        //右边数据的位置
        int rightIndex = middle + 1;
        //临时数据存放的位置
        int tempIndex = 0;
        //如果两堆都没有分完，那么继续循环，否则终止循环
        while (leftIndex <= middle && rightIndex <= right) {
            if (array[leftIndex] < array[rightIndex]) {
                temp[tempIndex++] = array[leftIndex++];
            } else {
                temp[tempIndex++] = array[rightIndex++];
            }
        }
        //如果左边的堆没有分完，将剩余的堆中的数据放入到临时存放数据的数组中
        while (leftIndex <= middle) {
            temp[tempIndex++] = array[leftIndex++];
        }
        //如果右边的堆没有分完，将剩余的堆中的数据放入到临时存放数据的数组中
        while (rightIndex <= right) {
            temp[tempIndex++] = array[rightIndex++];
        }
        //将数据放置到原来的数组中去
        tempIndex = 0;
        while (left <= right) {
            array[left++] = temp[tempIndex++];
        }
    }

}

结果为：[3, 3, 4, 6, 7, 7, 8, 9, 10]

来自算法