首页 > 代码库 > 归并排序
归并排序
算法思想：
分治法，将一个序列分为两部分，分别排序，然后合并已排序序列。
算法实现：
1 MERGE_SORT(A,p,r) 2 mid = (p+r)/2 3 MERGE_SORT(A,p,mid) 4 MERGE_SORT(A,mid,r) 5 MERGE(A,p,mid,r) 6 7 MERGE(A,p,mid,r) 8 create array A‘[r-p+1] 9 i = p10 j = mid11 k = 012 13 while i<mid and j <= r 14 do15 if A[i] <= A[j] then16 A‘[k++] = A[i++]17 else18 A‘[k++] = A[j++]19 20 while i < mid 21 do22 A‘[k++] = A[i++]23 24 while j <= r 25 do26 A‘[k++] = A[j++]27 28 copy array from A‘ to A
算法复杂度：
平均：O(nlgn)
最差：O(nlgn)
最优：O(nlgn)
空间复杂度:O(n)
使用场景：
归并排序由于有比较优的时间复杂度，并且具有排序稳定性(相同key值元素不改变位置)，因此一般用在要求稳定性的大规模数据排序中。
STL实现：
stl的stable_sort内部采用了归并算法实现，在有足够归并空间时，其复杂度为O(nlgn)，但当空间不足时，其复杂度为O(n lgn lgn )
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。