`
stinge
  • 浏览: 153830 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

合并排序(归并排序)

阅读更多

合并排序(归并排序)

 

合并排序是利用分治法的算法思想来解决排序问题的。

 

分治法:将原问题划分成n个规模较小而结构与原问题相似的子问题,递归的解决这些子问题,然后将结果合并。

 

基本思想:将序列分为两个子序列,并对两个子序列分别排序,之后将已排序子序列合并,即为排序结果,其中两个子序列的                 排序也按照分成更小的子序列,直至分解到单个元素,即为已排序子序列,然后合并。

 

算法描述:

 

 合并算法:

 

%将数组中两个已排序部分合并为一个
%数组,从而得到已排序的数组A
function A = my_merge(A,p,q,r)
%n1,n2为两个已排序的数组长度。
n1 = q - p +1;
n2 = r - q;
L = zeros(1,n1);
R = zeros(1,n2);
%将两个已排序部分分别复制到L,R
for i = 1:1:n1
    L(i) = A(p+i-1);
end
for j = 1:1:n2
    R(j) = A(q+j);
end
%问题转化为将L,R两个已排序数组,合并到数组A中。
%引进“哨兵”,简化代码
L(n1 + 1) = 500;
R(n2 + 1) = 500;
%每一次一定会加入元素,而且直至加入r-p+1个元素
%所以仅需一次循环
i = 1;
j = 1;
for k = p:1:r
    if L(i) < R(j)
        A(k) = L(i);
        i = i+1;
    else
        A(k) = R(j);
        j = j+1;
    end
end
 

 

排序:

 

 %合并排序A,从下标p到r

function A = my_merge_sort(A,p,r)
%如果p小于r,将数组分为两部分
%分别对各个部分调用排序函数,
%最后合并
if p < r
    q = floor((r + p)/2);
    my_merge_sort(A,p,q);   %排序前半部分
    my_merge_sort(A,q+1,r); %排序后半部分
    my_merge(A,p,q,r);      %合并
end
end
 

 

时间复杂度:o(n*logn)

 

 

 

 

 

 

 

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics