当前位置：首页 > news >正文

Java 归并排序算法详解

news 2024/11/13 4:19:15

Java 归并排序算法详解

归并排序（Merge Sort）是一种高效的、基于比较的排序算法，属于分治法的一种。本文将详细介绍归并排序的原理、Java 代码实现、时间复杂度分析和实际例子。

1. 归并排序原理

归并排序的基本思想是将待排序的序列分成若干个小序列，每个小序列单独排序，然后再将这些有序的小序列合并成一个整体有序的序列。具体步骤如下：

分解：将序列分成两个子序列。
解决：递归地对两个子序列进行归并排序。
合并：将两个有序的子序列合并成一个有序的序列。

2. Java 代码实现

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

public class MergeSort {// 归并排序方法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);}}// 合并两个有序的子序列private static void merge(int[] arr, int left, int mid, int right) {// 计算两个子序列的长度int n1 = mid - left + 1;int n2 = right - mid;// 创建临时数组int[] L = new int[n1];int[] R = new int[n2];// 复制数据到临时数组for (int i = 0; i < n1; i++) {L[i] = arr[left + i];}for (int j = 0; j < n2; j++) {R[j] = arr[mid + 1 + j];}// 合并临时数组到原数组int i = 0; // 初始索引 of 左子序列int j = 0; // 初始索引 of 右子序列int k = left; // 初始索引 of 合并后的子序列while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}// 复制左子序列的剩余元素while (i < n1) {arr[k] = L[i];i++;k++;}// 复制右子序列的剩余元素while (j < n2) {arr[k] = R[j];j++;k++;}}// 主方法，用于测试public static void main(String[] args) {int[] arr = {64, 34, 25, 12, 22, 11, 90};System.out.println("Original array:");printArray(arr);mergeSort(arr, 0, arr.length - 1);System.out.println("Sorted array:");printArray(arr);}// 辅助方法，用于打印数组public static void printArray(int[] arr) {for (int num : arr) {System.out.print(num + " ");}System.out.println();}
}

3. 时间复杂度分析

归并排序的时间复杂度如下：

最佳情况：时间复杂度为 O(nlog⁡n)
最坏情况：时间复杂度为 O(nlog⁡n)
平均情况：时间复杂度为 O(nlog⁡n)

4. 空间复杂度分析

归并排序的空间复杂度为 O(n)O(n)，因为需要额外的空间来存储临时数组。

5. 实际例子

我们可以通过一个具体的例子来理解归并排序的过程：

假设有一个数组 [64, 34, 25, 12, 22, 11, 90]，归并排序的过程如下：

分解：
- [64, 34, 25, 12, 22, 11, 90] 分解为 [64, 34, 25] 和 [12, 22, 11, 90]。
- [64, 34, 25] 继续分解为 [64, 34] 和 [25]。
- [12, 22, 11, 90] 继续分解为 [12, 22] 和 [11, 90]。
- [64, 34] 继续分解为 [64] 和 [34]。
- [12, 22] 继续分解为 [12] 和 [22]。
- [11, 90] 继续分解为 [11] 和 [90]。
合并：
- [64] 和 [34] 合并为 [34, 64]。
- [12] 和 [22] 合并为 [12, 22]。
- [11] 和 [90] 合并为 [11, 90]。
- [34, 64] 和 [25] 合并为 [25, 34, 64]。
- [12, 22] 和 [11, 90] 合并为 [11, 12, 22, 90]。
- [25, 34, 64] 和 [11, 12, 22, 90] 合并为 [11, 12, 22, 25, 34, 64, 90]。