Java版归并排序算法实现

• 1. merge函数的实现

private static void merge(int[] arr, int low, int mid, int high) {
    // 将要排序的数组片段复制出来
    int[] temp = Arrays.copyOfRange(arr, low, high + 1);
    // 左边数组的结束索引
    int end1 = mid - low;
    // 右边数组的结束索引
    int end2 = temp.length - 1;
    // 左边数组开始归并的索引
    int i = 0;
    // 右边数组开始归并的索引
    int j = end1 + 1;

    for (int k = low; k <= high; k++) {
        if (i > end1) {
            // 左边数组的归并指针率先超出了左边数组的范围
            // 则直接将右边剩下的所有数据全部复制过去即可
            arr[k] = temp[j];
            j++;
        } else if (j > end2) {
            // 右边数组的归并指针率先超出了右边数组的范围
            // 则直接将左边剩下的所有数据全部复制过去即可
            arr[k] = temp[i];
            i++;
        } else {
            // 正常归并
            if (temp[i] < temp[j]) {
                arr[k] = temp[i];
                i++;
            } else {
                arr[k] = temp[j];
                j++;
            }
        }
    }
}

• 2. 递归方式实现(自顶向下)的归并排序算法

public static void mergeSort(int[] arr, int low, int high) {
    if (low >= high) {
        return;
    }
    int mid = low + (high - low) / 2;
    mergeSort(arr, low, mid);
    mergeSort(arr, mid + 1, high);
    merge(arr, low, mid, high);
}

• 3. 借用栈实现循环方式(自顶向下)的归并排序算法

public static void mergeSort2(int[] arr) {
    if (arr.length <= 1) {
        return;
    }
    Stack<Integer> st = new Stack<>();
    int left = 0;
    int right = arr.length - 1;
    int center = left + (right - left) / 2;
    st.push(left);
    st.push(right);
    while (!st.isEmpty()) {
        int high = st.pop();
        int low = st.pop();
        int mid = low + (high - low) / 2;
        if (low < mid) {
            st.push(low);
            st.push(mid);
        }
        if (mid + 1 < high) {
            st.push(mid + 1);
            st.push(high);
        }
        merge(arr, low, mid, high);
    }
    merge(arr, left, center, right);
}

• 4. 不借用栈(自低向上)直接循环方式实现的归并排序算法
     这种方式可以实现对链表进行 Nlog(N)时间复杂度级别的排序

public static void mergeSort3(int[] arr) {
    for (int sz = 1; sz <= arr.length; sz += sz) {
        for (int i = 0; i + sz < arr.length; i += sz + sz) {
            int low = i;
            int mid = i + sz - 1;
            int high = Math.min(i + sz + sz - 1, arr.length - 1);
            merge(arr, low, mid, high);
        }
    }
}