AcWing 787. 归并排序
原题链接
简单
作者:
少年思无邪
,
2023-01-11 20:36:56
,
所有人可见
,
阅读 101
归并
void merge_sort(int nums[], int l, int r){
//递归终止情况
if(l == r)
return;
//第一步:分解成子问题
int mid = (l + r) >> 1;
//这里mid是向下取整的,所以使用mid作为分割线
//第二步:处理子问题
merge_sort(nums, l, mid);
merge_sort(nums, mid + 1, r);
//第三步:合并子问题
int k = 0, i = l, j = mid + 1, temp[r - l + 1];
while(i <= mid && j <= r){
if(nums[i] <= nums[j])
temp[k++] = nums[i++];
else
temp[k++] = nums[j++];
}
while(i <= mid)
temp[k++] = num[i++];
while(j <= r)
temp[k++] = nums[j++];
//最后需要将temp数组复制到原来的位置去
for(k = 0, i = l; i <= r; k++, i++)
nums[i] = temp[k];
}