题目描述
归并排序
bottom up 的解决方法,需要额外一个 O(N) 的空间复杂度
Top-down
使用递归的方法
时间复杂度
$O(nlog(n))$
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
const int N = 100005;
int nums[N];
int tmp[N];
void merge_sort(int* nums, int l, int r){
if(l>=r) return;
int mid = (l+r) >> 1;
merge_sort(nums, l, mid);
merge_sort(nums, mid+1, r);
int i=l;
int j=mid+1;
int k;
for(k = l; k<=r; k++){
// left exist
if(i<=mid && (nums[i] < nums[j] || j > r)){
tmp[k] = nums[i];
i++;
} else {
tmp[k] = nums[j];
j++;
}
}
for(k=l; k<=r; k++){
nums[k] = tmp[k];
}
return;
}
int main(){
int n;
scanf("%d", &n);
for(int i=0; i<n; i++){
scanf("%d", &nums[i]);
}
merge_sort(nums, 0, n-1);
for(int i=0; i<n; i++){
printf("%d", nums[i]);
if(i==n-1){
printf("\n");
}else{
printf(" ");
}
}
return 0;
}