本文主要是介绍排序算法之归并排序详细解读(附带Java代码解读),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
归并排序(Merge Sort)是一种稳定的排序算法,采用分治法(Divide and Conquer)的思想。它将一个数组分成两个子数组,分别对这两个子数组进行排序,然后将两个已排序的子数组合并成一个有序的数组。归并排序是一种高效的排序算法,尤其适合处理大规模数据。
算法思想
- 分解:将待排序的数组分成两个子数组,直到每个子数组只有一个元素(单个元素自然有序)。
- 解决:递归地对每个子数组进行排序。
- 合并:将两个已排序的子数组合并成一个有序的数组。
过程示例
假设有一个待排序的数组:[38, 27, 43, 3, 9, 82, 10]
步骤 1: 分解
将数组递归地分解成单个元素的数组:
- 初始数组:[38, 27, 43, 3, 9, 82, 10]
- 分解成:[38, 27, 43, 3] 和 [9, 82, 10]
- 进一步分解:
- [38, 27] 和 [43, 3]
- [38] 和 [27]
- [43] 和 [3]
- [9] 和 [82, 10]
- [82] 和 [10]
- [38, 27] 和 [43, 3]
- 进一步分解:
- 分解成:[38, 27, 43, 3] 和 [9, 82, 10]
步骤 2: 合并
将每对已排序的子数组合并成一个有序数组:
- 合并 [38] 和 [27]:[27, 38]
- 合并 [43] 和 [3]:[3, 43]
- 合并 [82] 和 [10]:[10, 82]
- 合并 [27, 38] 和 [3, 43]:[3, 27, 38, 43]
- 合并 [9] 和 [10, 82]:[9, 10, 82]
- 最终合并 [3, 27, 38, 43] 和 [9, 10, 82]:[3, 9, 10, 27, 38, 43, 82]
算法复杂度
-
时间复杂度:
- 最坏情况: O(n log n)
- 平均情况: O(n log n)
- 最佳情况: O(n log n)(即使数组已经排序,归并排序也会执行相同的操作)
-
空间复杂度: O(n) 归并排序需要额外的存储空间来保存合并结果。
优点
- 稳定性:归并排序是稳定的,即相等的元素在排序后相对位置不变。
- 时间复杂度优良:无论数据初始状态如何,归并排序的时间复杂度始终为 O(n log n)。
- 适用于大规模数据:适合大规模数据的排序,尤其是当数据不能完全加载到内存中时。
缺点
- 空间复杂度高:需要额外的 O(n) 空间来存储临时数组。
- 实现较复杂:相比其他简单排序算法(如插入排序),归并排序的实现较复杂。
Java代码解读
public class MergeSort {// 主方法:执行归并排序public static void mergeSort(int[] arr) {if (arr.length < 2) {return; // 数组长度小于2,直接返回}int mid = arr.length / 2;int[] left = new int[mid];int[] right = new int[arr.length - mid];// 分割数组System.arraycopy(arr, 0, left, 0, mid);System.arraycopy(arr, mid, right, 0, arr.length - mid);// 递归排序mergeSort(left);mergeSort(right);// 合并已排序的子数组merge(arr, left, right);}// 合并两个已排序的子数组private static void merge(int[] arr, int[] left, int[] right) {int i = 0, j = 0, k = 0;// 合并过程while (i < left.length && j < right.length) {if (left[i] <= right[j]) {arr[k++] = left[i++];} else {arr[k++] = right[j++];}}// 复制剩余元素while (i < left.length) {arr[k++] = left[i++];}while (j < right.length) {arr[k++] = right[j++];}}public static void main(String[] args) {int[] arr = {38, 27, 43, 3, 9, 82, 10};System.out.println("排序前的数组:");for (int num : arr) {System.out.print(num + " ");}System.out.println();mergeSort(arr);System.out.println("排序后的数组:");for (int num : arr) {System.out.print(num + " ");}}
}
代码说明
-
mergeSort方法:
- 递归地将数组分成两部分,分别对其进行排序。
- 使用
System.arraycopy
方法将数组分割成两个子数组left
和right
。 - 递归调用
mergeSort
对这两个子数组进行排序。 - 调用
merge
方法将排序后的子数组合并。
-
merge方法:
- 合并两个已排序的子数组
left
和right
。 - 使用三个指针
i
、j
和k
分别跟踪left
、right
和arr
数组的位置。 - 将较小的元素放入
arr
中,并移动对应的指针。 - 处理
left
和right
中剩余的元素。
- 合并两个已排序的子数组
-
main方法:
- 创建一个待排序的数组
arr
。 - 调用
mergeSort
方法对数组进行排序。 - 输出排序前和排序后的数组。
- 创建一个待排序的数组
这篇关于排序算法之归并排序详细解读(附带Java代码解读)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!