复杂度
时间复杂度(平均) | 时间复杂度(最好) | 时间复杂度(最坏) | 空间复杂度 | 稳定性 | 复杂性 |
---|---|---|---|---|---|
O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 | 较复杂 |
思路
- 采用分治思想,先"分"再"治"
- 分的过程即将数组分成若干个子部分,子部分最少数组元素为1
- 治的过程即将子部分进行合并,两两合并到一组
- 最终治到一组时排序结束
代码:
public int[] mergeSort_1(int[] nums, int l, int r){
if(l == r) return new int[]{nums[l]};//当分到子数组元素个数为1时返回该元素数组
int mid = (l + r) / 2;
int[] lArr = mergeSort_1(nums, l, mid);//左分
int[] rArr = mergeSort_1(nums, mid + 1, r);//右分
int[] merge = new int[r - l + 1];//合治数组
//合治 i,j,k分别处理lArr,rArr与merge的下标
int i = 0, j = 0, k = 0;
while(i < lArr.length && j < rArr.length){
if(lArr[i] < rArr[j]) merge[k++] = lArr[i++];
else merge[k++] = rArr[j++];
}
while(i < lArr.length){
merge[k++] = lArr[i++];
}
while(j < rArr.length){
merge[k++] = rArr[j++];
}
return merge;
}