归并排序 | IT蛋的个人博客

归并排序逻辑

归并排序（Merge Sort）是一种经典的排序算法，它使用分治思想将一个大问题分解为多个小问题，在递归过程中将这些小问题的答案合并成一个整体解决大问题。

具体来说，归并排序的步骤如下：

分解：将要排序的数组分解成两个子数组，直到每个子数组只有一个元素为止。
解决：对每个子数组进行排序，可以使用任何排序算法，通常使用归并排序本身递归地对子数组进行排序。
合并：将两个排好序的子数组合并成一个有序的数组。

在第一阶段中，将数组不断分割，直到每个子数组包含一个元素。这个阶段不会产生任何比较和交换操作，因此时间复杂度为 O(n)。

在第二阶段中，我们需要将每个子数组进行排序。由于每个子数组都已经是有序的，我们可以使用归并排序算法的特性——合并两个有序数组——来完成排序过程。由于每个子数组的大小为 n/2，因此排序时间复杂度为 O(nlogn)。

在第三阶段中，我们需要将两个排好序的子数组合并成一个有序的数组。这个过程需要创建一个临时的数组来存储结果，并且需要进行比较和移动元素的操作。因此时间复杂度为 O(n)。

整个排序过程的时间复杂度是 O(nlogn)，空间复杂度为 O(n)，稳定性好。

复杂度分析

时间复杂度：O(nlogn)

空间复杂度：O(n)

稳定性：好

代码实现

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(arr, 0, arr.length - 1);

        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);      // 对左半部分进行归并排序
            mergeSort(arr, mid + 1, right); // 对右半部分进行归并排序
            merge(arr, left, mid, right);   // 合并两个有序的子数组
        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[arr.length];
        int i = left; // 左半部分的起始位置
        int j = mid + 1; // 右半部分的起始位置
        int t = 0; // 临时数组的起始位置

        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }

        while (i <= mid) { // 将左半部分剩余元素填充进temp中
            temp[t++] = arr[i++];
        }

        while (j <= right) { // 将右半部分剩余元素填充进temp中
            temp[t++] = arr[j++];
        }

        t = 0;
        while (left <= right) { // 将temp中的元素全部拷贝到原数组中
            arr[left++] = temp[t++];
        }
    }
}

优点

稳定性： 归并排序是一种稳定的排序算法，相同元素的相对位置不会发生改变。
适应性强： 对各种数据分布场景都能够保持较好的排序性能。
并行化： 归并排序易于并行化实现，可以利用多核处理器进行并行排序，提高排序速度。
不受数据分布影响： 归并排序对数据的初始状态不敏感，在最坏情况下的时间复杂度也能得到保证。

缺点

额外空间开销： 归并排序需要额外的存储空间来存储临时数组，因此空间复杂度较高，可能会受限于内存容量。
性能稳定： 尽管归并排序的平均时间复杂度为 O(nlogn)，但在实际情况下，归并排序的常数项较大，导致在小规模数据集上性能不如快速排序等算法。
非原地排序： 归并排序通常需要额外的存储空间来存储临时数据，因此是一种非原地排序算法，可能会增加程序的运行开销。

使用场景

大规模数据排序： 归并排序适用于需要对大规模数据集进行排序的情况，由于其稳定的时间复杂度 O(nlogn)，在处理大量数据时表现优异。
外部排序： 当数据无法一次性载入内存而需要借助外部存储进行排序时，归并排序是一个理想的选择，因为它可以通过多次读取和写入磁盘来排序大型文件或数据流。