归并排序

基本介绍

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法，该算法采用经典的分治(divide-and-conquer)策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之）。

视频讲解

代码实现

// 归并排序
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
    if (left < right) {
        int mid = (left + right) / 2; // 中间索引
        // 向左递归进行分解
        mergeSort(arr, left, mid, temp);
        // 向右递归进行分解
        mergeSort(arr, mid + 1, right, temp);
        // 合并
        merge(arr, left, mid, right, temp);
    }
}
/**
 * 合并有序数组
 *
 * @param arr   排序的原始数组
 * @param left  左边有序数组的初始索引
 * @param mid   中间索引
 * @param right 右边索引
 * @param temp  中转数组
 */
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
    int i = left; // 左边有序数组的初始索引
    int j = mid + 1; // 右边有序数组的初始索引
    int t = 0; // 指向 temp 数组的当前索引
    // 先把左右两边的有序数据按照规则填充到 temp数组
    // 直到左右两边的有序序列,有一边处理完毕为止
    while (i <= mid && j <= right) {
        // 如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
        // 即将左边的当前元素,填充到 temp数组
        if (arr[i] <= arr[j]) {
            temp[t] = arr[i];
            t++;
            i++;
        } else { // 反之,将右边有序序列的当前元素,填充到temp数组
            temp[t] = arr[j];
            t++;
            j++;
        }
    }
    // 把有剩余数据的一边的数据依次全部填充到temp
    while (i <= mid) {
        temp[t] = arr[i];
        t++;
        i++;
    }
    while (j <= right) {
        temp[t] = arr[j];
        t++;
        j++;
    }
    // 将 temp数组的元素拷贝到 arr
    // 注意,并不是每次都拷贝所有
    t = 0;
    int tempLeft = left;
    while (tempLeft <= right) {
        arr[tempLeft] = temp[t];
        t++;
        tempLeft++;
    }
}

使用时要实例化 temp 数组

int[] temp = new int[arr.length];