了解归并排序算法（附Java示例）

合并排序：综合指南

合并排序是一种高效的排序算法，经常在各种编程语言中使用，无论是独立的还是作为混合方法的一部分。 它的基础在于分而治之的范式：一个问题被分解成更小的子问题，单独解决，然后将它们的解决方案组合起来得到最终结果。 合并排序递归地将输入列表分成两半，对每一半进行排序，然后合并已排序的两半以生成完全排序的列表。

理解合并排序过程

让我们使用示例数组来说明合并排序过程：

此图描绘了数组的递归划分。

此图显示了排序子数组的合并。

实现合并排序

下面是归并排序算法的 Java 实现：

import java.util.Arrays;

public class MergeSortTest {
    public static void main(String[] args){
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        mergeSort(arr, 0, arr.length-1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    static void mergeSort(int arr[], int start, int end){
        if (start < end){
            int mid = (start + end) / 2;
            mergeSort(arr, start, mid);
            mergeSort(arr, mid + 1, end);
            merge(arr, start, mid, end);
        }
    }

    static void merge(int arr[], int start, int mid, int end){
        int[] left = new int[(mid - start) + 1];
        int[] right = new int[end - mid];

        for(int i = 0; i <= mid - start; i++)
            left[i] = arr[start + i];
        for(int j = 0; j < end - mid; j++)
            right[j] = arr[mid + 1 + j];

        int i = 0, j = 0;
        int k = start;

        while (i < left.length && j < right.length){
            if(left[i] <= right[j]){
                arr[k] = left[i];
                i++;
            }
            else{
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        while (i < left.length){
            arr[k] = left[i];
            i++;
            k++;
        }

        while (j < right.length){
            arr[k] = right[j];
            j++;
            k++;
        }
    }
}

代码说明

mergeSort 方法递归地划分数组，直到子数组仅包含一个元素。 merge 方法至关重要；它获取已排序的子数组并将它们有效地合并为单个已排序的数组。 合并过程涉及比较两个子数组中的元素并将较小的元素放入主数组中。

此图说明了合并步骤。

代码的输出是：

未排序数组：[8,2,6,4,9,1] 排序数组：[1, 2, 4, 6, 8, 9]

算法复杂度

• 时间复杂度： 在所有情况下（最佳、平均和最差）O(n log n)。这是因为无论输入数组的初始顺序如何，分治方法都保持一致。
• 空间复杂度： O(n)，因为合并操作期间临时数组需要额外的空间。

以上是了解归并排序算法（附Java示例）的详细内容。更多信息请关注PHP中文网其他相关文章！