归并排序分析
一、代码实现
void merge(int*a,int low,int mid,int high){
int *b = new int [high-low+1];
int i=low,j=mid+1,k=0;
while (i<=mid&&j<=high){
if(a[i]<a[j]){
b[k++] = a[i++];
} else
b[k++] = a[j++];
}
while (i<=mid)
b[k++] = a[i++];
while (j<=high)
b[k++] = a[j++];
k=0;
for (int l = low; l <=high; ++l) {
a[l] = b[k++];
}
delete []b;
}
void merge_sort(int*a,int low,int high){
if(low==high)
return;
else {
int mid = (low+high)/2;
merge_sort(a, low, mid);
merge_sort(a,mid+1,high);
merge(a,low,mid,high);
}
}
思路讲解
把一个数组分为左右两段,分别对其进行排序,则接下来只需要对两个有序数组合并即可
二、复杂度
时间复杂度:O(N*log_2N)
空间复杂度:O(N)
- 时间复杂度:归并排序会对数组做二分分割,合并时对数组元素进行遍历,所以时间复杂度为O(N*log_2N)
- 空间复杂度:主要来自两个方面,一个是递归分割时调用栈帧log_2N,一个是合并数组时额外开的数组N,则空间复杂度为O(N)