归并排序

算法思想

这个算法中基本的操作是合并两个已排序的数组，取两个输入数组 A 和 B，一个输出数组 C，以及三个计数器 i、j、k，它们初始位置置于对应数组的开始端。
A[i] 和 B[j] 中较大者拷贝到 C 中的下一个位置，相关计数器向前推进一步。
当两个输入数组有一个用完时候，则将另外一个数组中剩余部分拷贝到 C 中。

归并排序.png

我的理解

一个数组从中间拆分，不断的递归拆分，直到不能拆分为止，然后再递归合并排序，直至合并为一个数组。

java代码的实现

/**
 * Author: 编程的猫 iCat
 * Emil: 15827348069@163.com
 * Date: 3/31/21 12:11 PM
 * Desc: 归并排序
 */
public class MergeSort {


    /**
     * 归并排序思想：两个数组排序合并称为一个数组
     *
     * @param array 数组
     * @param left  left
     * @param mid   mid
     * @param right right
     */
    private static void merge_(int[] array, int left, int mid, int right) {

        //拷贝数组
        int[] temp = Arrays.copyOfRange(array, left, right + 1);

        //初始化其实索引
        int i = left, j = mid + 1;
        for (int k = left; k <= right; ++k) {

            if (i > mid) {//左边数组已经排序完毕
                array[k] = temp[j-left];
                j++;
            } else if (j > right) {//右边的数组已经排序完毕
                array[k] = temp[i-left];
                i++;
            } else if (temp[i-left] < temp[j-left]) {
                array[k] = temp[i-left];
                i++;
            } else {
                array[k] = temp[j-left];
                j++;
            }
        }

    }

    /**
     * @param array 数组
     * @param left  数组左边的索引
     * @param right 数组右边的索引
     */
    private static void sort_(int[] array, int left, int right) {

        if (left >= right) {
            return;
        }

        int mid = (left + right) >> 1;

        sort_(array, left, mid);
        sort_(array, (mid + 1), right);

        if (array[mid] > array[mid + 1]) {
            merge_(array, left, mid, right);
        }
    }

    /**
     * 归并排序
     *
     * @param array 数组
     */
    public static void sort(int[] array) {
        int len = array.length;
        sort_(array, 0, len - 1);
    }


}

C++代码的实现

//归并排序
void mergeSort_(int array[], int left, int mid, int right) {

    //拷贝数组
    int temp[right - left + 1];

    for (int i = left; i <= right; ++i) {
        temp[i - left] = array[i];
    }

    int i = left, j = mid + 1;
    for (int k = left; k <= right; ++k) {

        if (i > mid) {
            //左边数组已经完成排序
            array[k] = temp[j - left];
            j++;
        } else if (j > right) {
            //右边数组已经完成排序
            array[k] = temp[i - left];
            i++;
        } else if (temp[i - left] > temp[j - left]) {
            array[k] = temp[j - left];
            j++;
        } else {
            array[k] = temp[i - left];
            i++;
        }
    }

}

void merge(int array[], int left, int right) {
    if (left >= right)return;

    int mid = (left + right) >> 1;

    merge(array, left, mid);
    merge(array, mid + 1, right);

    if (array[left] > array[right]) {
        mergeSort_(array, left, mid, right);
    }

}

void mergeSort(int array[], int len) {

    merge(array, 0, len - 1);

}