时间复杂度: O(nlogn)空间复杂度: O(n)稳定性: 稳定实现语言: C/C++
原理思想这里采用的是分治的思想,但与快速排序相反的是,归并排序采用的是先分治再合并。
已知在有额外空间的情况下,合并两个有序数组得到一个新的较长有序数组是很高效的。 所以能不能把一个任意数组分成由左右两个有序数组组成然后合并成有序数组呢?
显然不能,大部分情况并不能分成两个有序数组,但如果在此之前用同样的方法(这里采用递归)事先排序左右两部分呢?大部分情况依然不能,因此这个递归会一直递推下去,最终待排序区间不断缩小,到只剩一个或零个元素,此时就可以将其看为有序数组了,也就是说递归在这里停止,可以一路合并有序数组一路回归上去了
分治这里使用左右指针控制待排序区间(迭代器也行),并采用递归的方式形象地完成分治操作
123456789101112131415161718void _MergeSort(vector<int>& arr,int left,int right,vector<int>&tmp){ //分治 if(le ...