mergeSort 归并排序

1. 基本描述

​ 将两个 有序 的数列 合并成一个有序数列。归并排序的核心就是这么一句话。

​ 这里有两个重点

1. 前提 有序数列
2. 合并

​ 问题就在这里，一个无序的数组怎么前提是有序。

​ 一个数的数列就是有序。

这就涉及到归并排序算法细节了。

时间复杂度
$$
O(nlog_2n)
$$
​ 空间复杂度
$$
T(n)
$$
​

2.算法流程

1. 从上往下分解

2. 从下往上归并

   所以归并排序，在其名字中其实忽略了分解。那么同样采用递归实现。

   

3. 算法实现

从上往下分解

   private static void merge(int[] array, int l, int r){if(l==r) {return ;}int mid=(l+r)/2;merge(array,l,mid);merge(array,mid+1,r);mergeSort(array,l,mid+1,r);}

​ 归并算法

1. 扩充
2. 拷贝
3. 归并
4. 处理尾部

    private static void mergeSort(int[] array, int l, int mid, int r) {int  [] left=new int [mid-l];int []right=new int [r-mid+1];System.arraycopy(array,l,left,0,left.length);System.arraycopy(array,mid,right,0,right.length);int i=0,j=0;int post=l;while(i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！