mergeSort 歸并排序

1. 基本描述

? 將兩個 有序 的數列 合并成一個有序數列。歸并排序的核心就是這么一句話。

? 這里有兩個重點

前提 有序數列

合并

? 問題就在這里，一個無序的數組怎么前提是有序。

? 一個數的數列就是有序。

這就涉及到歸并排序算法細節了。

時間復雜度
$$
O(nlog_2n)
$$
? 空間復雜度
$$
T(n)
$$
?

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);}

? 歸并算法

擴充

拷貝

歸并

處理尾部

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<left.length&&j<right.length){if(left[i]<right[j])array[post]=left[i++];elsearray[post]=right[j++];post++;}for (;i<left.length;i++)array[post++]=left[i];for (;j<right.length;j++)array[post++]=right[j];}

轉載于:https://www.cnblogs.com/EsMussSeinHui/p/11303966.html

總結

以上是生活随笔為你收集整理的# mergeSort 归并排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。