介绍

归并排序是创建在归并操作上的一种有效的排序算法,效率为O(nlogn),1945年由冯·诺伊曼首次提出。归并排序算法主要依赖归并(Merge)操作。归并操作指的是将两个已经排序的序列合并成一个序列的操作。本文主要介绍递归法。

时间复杂度:

  • 最好情况:O(nlogn)
  • 平均情况:O(nlogn)
  • 最坏情况:O(nlogn)

稳定性:稳定

额外的空间:O(n)

过程

递归操作

  1. 将待排序元素分为大致相同的两个子集合
  2. 重复步骤1直到每个子集合仅包含1个或0个元素
  3. 对两个子集合分别进行排序
  4. 合并两个已排序的子序列
  5. 得到排序结果

归并操作

  1. 创建左右两个临时数组
  2. 依次比较两个数组的元素,并将较小的元素放回原数组
  3. 重复步骤2直到所有元素都放回原数组
  4. 合并完成

以上内容可能比较抽象(主要是我表达能力比较垃圾),用图示可能比较好理解:

宏观过程:

Java实现

/*
 * MergeSort.java:归并排序(递归实现)
 */
import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] a = new int[]{9, 2, 5, 6, 7, 2, 4, 5};
        sort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    private static void sort(int[] arr, int left, int right) {
        //递归跳出条件:左边索引大于右边索引
        if (left >= right) {
            return;
        }
        int mid = (right + left) / 2;//中间位置索引
        //从左往右递归
        sort(arr, left, mid);
        sort(arr, mid + 1, right);
        merge(arr, left, right, mid);//合并已排序好的数组

    }

    /**
     * 归并操作
     * @param arr 待排序数组
     * @param left 数组左边索引
     * @param right 数组右边索引
     * @param mid 数组中间索引
     */
    private static void merge(int[] arr, int left, int right, int mid) {
        int leftLength = mid - left + 1;//左边数组长度
        int rightLength = right - mid;//右边数组长度
        //注意:int最大值标记位用于合并操作时,当遍历到某一数组(左或右)最后一位时,无法继续与另一位比较,因此引入此标记位用于比较
        int[] leftArr = new int[leftLength + 1];//左边临时数组,增加一位为int最大值标记位
        int[] rightArr = new int[rightLength + 1];//右边临时数组,增加一位为int最大值标记位
        for (int i = 0; i < leftLength; i++) {
            leftArr[i] = arr[left + i];//将元素存入临时数组
        }
        for (int i = 0; i < rightLength; i++) {
            rightArr[i] = arr[mid + i + 1];//将元素存入临时数组
        }
        leftArr[leftLength] = Integer.MAX_VALUE;//临时数组最后一位取int最大值
        rightArr[rightLength] = Integer.MAX_VALUE;//临时数组最后一位取int最大值
        int i = 0, j = 0;//左右临时数组索引标记
        //合并数组,依次将小的放在数组左边
        for (int k = left; k <= right; k++) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k] = leftArr[i];
                i++;
            } else {
                arr[k] = rightArr[j];
                j++;
            }
        }
    }
}
最后修改:2021 年 04 月 18 日
如果觉得我的文章对你有用,请随意赞赏