简介

归并排序（Merge Sort）是一种高效的排序算法，它基于分治策略。它将待排序的数组递归地分成两个子数组，分别对子数组进行排序，然后将两个有序子数组合并成一个有序数组。

归并排序可以通过两种不同的方式实现：自上而下的递归和自下而上的迭代。

算法图例

自上而下的递归-实现步骤

  • 将数组不断二分，直到分割成单个元素的子数组（递归的"分"）。

  • 递归地将相邻的子数组进行合并，直到最终合并成一个有序数组（递归的"治"）。

  • 合并两个子数组时，需要创建一个临时数组来存储合并后的结果。比较两个子数组的元素，将较小（或较大）的元素依次放入临时数组中，直到其中一个子数组被完全放入。然后将剩余的子数组中的元素直接放入临时数组中。

  • 将临时数组中的元素复制回原始数组的对应位置，完成合并。

自上而下的递归-实现示例

以下是一个使用Java实现归并排序算法的示例代码：

public class MergeSort {
    public static void mergeSort(int[] array) {
        int n = array.length;
        if (n <= 1) {
            return;
        }
        int[] temp = new int[n];
        mergeSortRecursive(array, temp, 0, n - 1);
    }
​
    public static void mergeSortRecursive(int[] array, int[] temp, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        mergeSortRecursive(array, temp, left, mid);
        mergeSortRecursive(array, temp, mid + 1, right);
        merge(array, temp, left, mid, right);
    }
​
    public static void merge(int[] array, int[] temp, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = array[i++];
        }
        while (j <= right) {
            temp[k++] = array[j++];
        }
        for (i = left, k = 0; i <= right; i++, k++) {
            array[i] = temp[k];
        }
    }
​
    public static void main(String[] args) {
        int[] array = {5, 2, 8, 12, 1, 6, 3, 9};
        System.out.println("Original array: " + Arrays.toString(array));
        mergeSort(array);
        System.out.println("Sorted array: " + Arrays.toString(array));
    }
}

在上面的代码中，mergeSort方法实现了归并排序算法。它使用了递归的方式将数组进行分割，并通过mergeSortRecursive方法对子数组进行排序。在mergeSortRecursive方法中，先递归地将左右子数组分别排序，然后再通过merge方法将两个有序子数组合并成一个有序数组。

在merge方法中，我们使用两个指针i和j分别指向两个子数组的起始位置，比较元素大小并将较小的元素放入临时数组temp中，直到其中一个子数组被完全放入。然后将剩余的子数组中的元素直接放入临时数组中。最后，将临时数组中的元素复制回原始数组的对应位置。

自下而上的迭代-实现步骤

  • 将数组划分为大小为1的子数组。

  • 依次将相邻的子数组合并成一个更大的有序子数组，直到合并完成得到最终的有序数组。

自下而上的迭代-实现示例

public class MergeSort {
    public static void mergeSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        int[] temp = new int[array.length];
        int stepSize = 1;
        while (stepSize < array.length) {
            int left = 0;
            while (left + stepSize < array.length) {
                int mid = left + stepSize - 1;
                int right = Math.min(left + 2 * stepSize - 1, array.length - 1);
                merge(array, temp, left, mid, right);
                left += 2 * stepSize;
            }
            stepSize *= 2;
        }
    }
​
    // 合并两个有序子数组
    public static void merge(int[] array, int[] temp, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = array[i++];
        }
        while (j <= right) {
            temp[k++] = array[j++];
        }
        for (i = left, k = 0; i <= right; i++, k++) {
            array[i] = temp[k];
        }
    }
​
    public static void main(String[] args) {
        int[] array = {5, 2, 8, 12, 1, 6, 3, 9};
        System.out.println("Original array: " + Arrays.toString(array));
        mergeSort(array);
        System.out.println("Sorted array: " + Arrays.toString(array));
    }
}

在上述代码中，mergeSort方法是归并排序的入口方法，它使用一个while循环进行迭代排序。首先将数组划分为大小为1的子数组，然后依次将相邻的子数组两两合并成一个更大的有序子数组，直到最终得到排序完成的数组。