归并排序

归并排序

归并排序的时间复杂度任何情况下都是 O(nlogn)，看起来非常优秀。（即便是快速排序，最坏情况下，时间复杂度也是 O(n2)。）

但是，归并排序并没有像快排那样，应用广泛，这是为什么呢？因为它有一个致命的“弱点”，那就是归并排序不是原地排序算法。

这是因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间。这一点你应该很容易理解。那我现在问你，归并排序的空间复杂度到底是多少呢？是 O(n)，还是 O(nlogn)，应该如何分析呢？

实际上，递归代码的空间复杂度并不能像时间复杂度那样累加。刚刚我们忘记了最重要的一点，那就是，尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。

左右2个有序数组开始并成一个新的有序数组

code

//有序数组的合并void merge(int arr[],int m,int n){    int len=n-m+1;    int i=m;    int mid=(m+n)/2;    int j=mid+1;    int *tmparr=malloc(sizeof(int)*len);    int index=0;    while(i<=mid && j<=n){        if(arr[i]<arr[j]){            tmparr[index++]=arr[i++];        } else if(arr[j]<arr[i]){            tmparr[index++]=arr[j++];        }else{            tmparr[index++]=arr[i++];            tmparr[index++]=arr[j++];        }    }    while(i<=mid){        tmparr[index++]=arr[i++];    }    while(j<=n){        tmparr[index++]=arr[j++];    }    int k=0;    for(;k<index;k++){        arr[m+k]=tmparr[k];    }    free(tmparr);}//归并排序void mergeSort(int arr[],int m,int n){    if(m>=n){        return;    }    int mid=(m+n)/2;    mergeSort(arr,m,mid);    mergeSort(arr,mid+1,n);    merge(arr,m,n);}

左右2个有序数组开始并成一个新的有序数组

更多相关文章

随机推荐