【算法-归并】

2024-08-30 16:28

文章标签 算法归并

本文主要是介绍【算法-归并】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

定义

归并排序（Merge Sort）是一种基于分治思想的高效排序算法，它的基本思想是将一个无序的数组分成两个子数组，分别对这两个子数组进行排序，然后将排序好的子数组合并成一个有序的数组。

基本步骤

1. 分解（Divide）

目标：将数组递归地分成两个子数组，直到每个子数组只有一个元素或为空。

对于给定的无序数组 arr[]，选择一个中间点 mid 将数组分为两部分：arr[0…mid] 和 arr[mid+1…n-1]。
对这两个子数组分别进行归并排序。这个过程会递归地进行，直到每个子数组只包含一个元素。
示例：

原始数组：[38, 27, 43, 3, 9, 82, 10]
第一次分解：[38, 27, 43, 3] 和 [9, 82, 10]
第二次分解：[38, 27] 和 [43, 3] 以及 [9] 和 [82, 10]
第三次分解：[38] 和 [27] 以及 [43] 和 [3] 以及 [82] 和 [10]
当数组被分解成单个元素时，分解过程结束。

2. 合并（Conquer）

目标：将两个有序的子数组合并成一个有序的数组。这个过程会逐步将分解的数组合并回去，直到原始数组被完全合并。
在合并的过程中，我们会创建两个指针，分别指向两个子数组的起始位置，然后比较这两个位置上的元素，将较小的元素放入结果数组中，并移动指针。
重复这个过程，直到两个子数组的所有元素都被合并。
示例：

合并 [38] 和 [27] -> [27, 38]
合并 [43] 和 [3] -> [3, 43]
合并 [82] 和 [10] -> [10, 82]
合并 [27, 38] 和 [3, 43] -> [3, 27, 38, 43]
合并 [3, 27, 38, 43] 和 [9, 10, 82] -> [3, 9, 10, 27, 38, 43, 82]

特点

时间复杂度：每次分解的时间复杂度是O(log n)，合并的时间复杂度是O(n)，因此总的时间复杂度为O(n log n)。
空间复杂度：需要额外的空间来存储临时子数组，因此空间复杂度为O(n)。
稳定性：归并排序是一种稳定的排序算法。

代码

public class MergeSort {// 主函数，用于测试归并排序public static void main(String[] args) {int[] array = {38, 27, 43, 3, 9, 82, 10};mergeSort(array, 0, array.length - 1);// 输出排序后的数组System.out.println("排序后的数组：");for (int i = 0; i < array.length; i++) {System.out.print(array[i] + " ");}}// 归并排序的主函数public static void mergeSort(int[] array, int left, int right) {if (left < right) {// 找到中间点int mid = (left + right) / 2;// 递归地对左半部分进行排序mergeSort(array, left, mid);// 递归地对右半部分进行排序mergeSort(array, mid + 1, right);// 合并两个排序好的子数组merge(array, left, mid, right);}}// 合并两个有序子数组的函数public static void merge(int[] array, int left, int mid, int right) {// 找出两个子数组的大小int n1 = mid - left + 1;int n2 = right - mid;// 创建临时数组int[] leftArray = new int[n1];int[] rightArray = new int[n2];// 拷贝数据到临时数组for (int i = 0; i < n1; i++) {leftArray[i] = array[left + i];}for (int j = 0; j < n2; j++) {rightArray[j] = array[mid + 1 + j];}// 归并临时数组int i = 0, j = 0;  // 初始化两个子数组的索引int k = left;  // 初始化合并子数组的索引while (i < n1 && j < n2) {if (leftArray[i] <= rightArray[j]) {array[k] = leftArray[i];i++;} else {array[k] = rightArray[j];j++;}k++;}// 复制leftArray剩余元素while (i < n1) {array[k] = leftArray[i];i++;k++;}// 复制rightArray剩余元素while (j < n2) {array[k] = rightArray[j];j++;k++;}}
}

分解阶段：
- mergeSort(array, left, right) 是一个递归函数，它将数组 array 从索引 left 到 right 进行分解。
- 通过 mid = (left + right) / 2 计算数组的中间点，然后分别递归调用 mergeSort 对左半部分和右半部分进行排序。
合并阶段：
- merge(array, left, mid, right) 函数将两个已经排序的子数组 array[left…mid] 和 array[mid+1…right] 合并成一个有序的数组。
- 在合并时，会创建两个临时数组 leftArray 和 rightArray 分别存储两个子数组，然后逐一比较两个子数组的元素，将较小的元素放回到原数组中。
- 最后，将剩余的元素复制回原数组。