- 算法思想
歸并排序中使用分治法。將原來的問題劃分成子問題，然后遞歸求解子問題，然后再合并這些子問題的解硫戈。 - 時間復(fù)雜度
歸并排序無論什么情況都是O(nlgn)
可以理解為每個要?dú)w并排序的數(shù)組大致會被分成lgn層。每一層都有n個元素
例如歸并排序數(shù)組
int[] num = {32,2,1,6,23,11,10,43,2};
最開始通過數(shù)組下標(biāo)low=0和長度high=8找到中間值mid=(low+high)/2酌壕。此時把原問題分解成2個子問題掏愁，然后再對兩個子問題進(jìn)行歸并排序。先把0-mid子數(shù)組排序卵牍，然后mid+1-high排序
public static int[] mergeSort(int[] num,int low,int high) {
int mid = (low+high)/2;
if (low<high) {
mergeSort(num, low, mid);
mergeSort(num, mid+1, high);
mergeSort( num, low, mid,high);
}
return num;
}
private static void mergeSort(int[] num, int low, int mid, int high) {
int[] temp = new int[high-low+1];
int i=low;
int j=mid+1;
int k=0;
while(i<=mid&&j<=high){
if (num[i]<num[j]) {
temp[k++]=num[i++];
}else {
temp[k++]=num[j++];
}
}
while(i<=mid){
temp[k++]=num[i++];
}
while(j<=high){
temp[k++]=num[j++];
}
for (int k2 = 0; k2 < temp.length; k2++) {
num[k2+low]=temp[k2];
}
}
