JAVA十大排序算法之归并排序详解

一、概述

归并排序是一种高效稳定的排序算法，它将待排序的序列分成若干个子序列，每个子序列都是有序的，然后再将有序的子序列合并成整体有序的序列。由于归并排序是基于比较的排序算法，因此时间复杂度为 O(nlogn)。

二、算法流程

归并排序算法分为两个过程：分治和合并。

1. 分治：将待排序的序列平分成两个子序列，对左右两个子序列分别进行递归排序。当子序列长度小于等于1时，停止递归。

2. 合并：将排好序的左右子序列合并成一个有序的序列。

三、JAVA代码实现

public static void mergeSort(int[] arr, int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        // 递归分治
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);
        // 合并子序列
        merge(arr, low, mid, high);
    }
}

private static void merge(int[] arr, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    int i = low;
    int j = mid + 1;
    int k = 0;
    // 比较左右子序列，合并成一个有序的序列
    while (i <= mid && j <= high) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= high) {
        temp[k++] = arr[j++];
    }
    // 将临时数组中的元素复制到原数组中
    for (int m = 0; m < temp.length; m++) {
        arr[low + m] = temp[m];
    }
}

在上面的代码中，mergeSort() 方法是归并排序的入口方法，merge() 方法是合并两个子序列的方法。

四、示例说明

示例一

对于待排序序列 [5, 3, 6, 8, 4, 2]，按照归并排序的流程，分别进行以下操作：

1. 分治：将待排序的序列分成 [5, 3, 6] 和 [8, 4, 2] 两个子序列，对子序列进行递归排序。

   • [5, 3, 6] ：将子序列分成 [5, 3] 和 [6] 两个子序列，对子序列进行递归排序。

     • [5, 3] ：将子序列分成 [5] 和 [3] 两个子序列，对子序列进行递归排序。

       • [5] 和 [3] 都只有一个元素，递归终止。

     • [6] ：只有一个元素，递归终止。

   • [8, 4, 2] ：将子序列分成 [8] 和 [4, 2] 两个子序列，对子序列进行递归排序。

     • [4, 2] ：将子序列分成 [4] 和 [2] 两个子序列，对子序列进行递归排序。

       • [4] 和 [2] 都只有一个元素，递归终止。

     • [8] ：只有一个元素，递归终止。

2. 合并：将排好序的子序列合并成有序的序列。首先将 [5] 和 [3] 合并成 [3, 5]，然后将 [6] 和 [3, 5] 合并成 [3, 5, 6]。将 [4] 和 [2] 合并成 [2, 4]，然后将 [8] 和 [2, 4] 合并成 [2, 4, 8]。最后将 [3, 5, 6] 和 [2, 4, 8] 合并成 [2, 3, 4, 5, 6, 8]。完成排序。

示例二

对于待排序序列 [7, 4, 3, 8, 1, 5]，按照归并排序的流程，分别进行以下操作：

1. 分治：将待排序的序列分成 [7, 4, 3] 和 [8, 1, 5] 两个子序列，对子序列进行递归排序。

   • [7, 4, 3] ：将子序列分成 [7] 和 [4, 3] 两个子序列，对子序列进行递归排序。

     • [4, 3] ：将子序列分成 [4] 和 [3] 两个子序列，对子序列进行递归排序。

       • [4] 和 [3] 都只有一个元素，递归终止。

     • [7] ：只有一个元素，递归终止。

   • [8, 1, 5] ：将子序列分成 [8] 和 [1, 5] 两个子序列，对子序列进行递归排序。

     • [1, 5] ：将子序列分成 [1] 和 [5] 两个子序列，对子序列进行递归排序。

       • [1] 和 [5] 都只有一个元素，递归终止。

     • [8] ：只有一个元素，递归终止。

2. 合并：将排好序的子序列合并成有序的序列。首先将 [4, 3] 和 [7] 合并成 [3, 4, 7]，然后将 [1] 和 [5] 合并成 [1, 5]，最后将 [3, 4, 7] 和 [1, 5, 8] 合并成 [1, 3, 4, 5, 7, 8]。完成排序。

五、总结

归并排序是一种高效稳定的排序算法，时间复杂度为 O(nlogn)，比较适合对大规模数据的排序。在实际应用中，由于归并排序需要合并两个有序的子序列，所以需要额外的存储空间来存储这些子序列。