算法思想
歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表饼煞，即把待排序序列分為若干個子序列源葫，每個子序列是有序的。然后再把有序子序列合并為整體有序序列砖瞧。
算法步驟
- 申請空間息堂，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列
- 設定兩個指針块促，最初位置分別為兩個已經(jīng)排序序列的起始位置
- 比較兩個指針所指向的元素荣堰，選擇相對小的元素放入到合并空間，并移動指針到下一位置
重復步驟3直到某一指針超出序列尾 - 將另一序列剩下的所有元素直接復制到合并序列尾
歸并排序示例
算法復雜度
- 時間復雜度為O(nlog?n) 這是該算法中最好竭翠、最壞和平均的時間性能振坚。
- 空間復雜度為 O(n)
算法穩(wěn)定性
歸并排序比較占用內存，但卻是一種效率高且穩(wěn)定的算法逃片。
算法實現(xiàn)
public void mergeSort(int[] arr,int left,int right){
if(left >= right){
return;
}
int center = (right + left)/2;
mergeSort(arr,left,center);
mergeSort(arr,center + 1,right);
merge(arr,left,right,center);
}
private void merge(int[] arr,int left,int right,int center){
int[] tmpArr = new int[right - left + 1]; //存儲排序結果
int tmpIndex = 0;
int start1 = left;
int start2 = center + 1;
while(start1 <= center && start2 <= right){
if(arr[start1] < arr[start2]){
tmpArr[tmpIndex++] = arr[start1++];
}else{
tmpArr[tmpIndex++] = arr[start2++];
}
}
while(start1 <= center){
tmpArr[tmpIndex++] = arr[start1++];
}
while(start2 <= right){
tmpArr[tmpIndex++] = arr[start2++];
}
tmpIndex = 0;
while(left <= right){
arr[left++] = tmpArr[tmpIndex++];
}
}
