xiaoy的个人博客分享 http://blog.sciencenet.cn/u/xiaoy

博文

[用MATLAB写算法]之排序算法2)归并排序merge sort

已有 3241 次阅读 2017-3-29 18:28 |个人分类:算法学习|系统分类:科研笔记

归并排序(merge sort)是一种利用分治策略(divide and conquer)进行排序的算法,算法复杂度为 $\Theta (nlog_{2}n)$ .


filename: merge_sort

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function result=merge_sort(num_array)
% result=merge_sort(num_array)  ascending
% algorithm complexity: theta(n*log2(n))

N=length(num_array);

% split num_array to two sub sorted array
if floor(N/2)>=2
   sub_sorted_l=merge_sort(num_array(1:floor(N/2)));
   sub_sorted_r=merge_sort(num_array(floor(N/2)+1:N));
       
else % sub array with no more than 2 elements
   sub_sorted_l=num_array(1);
   sub_sorted_r=num_array(2:end);
   if length(sub_sorted_r)>1  % sort sub_sorted_r which has 2 elements
       if sub_sorted_r(1)>sub_sorted_r(2)
           sub_sorted_r([1 2])=sub_sorted_r([2 1]);
       end
   end
end
   


kl=1;   % index for sub_sorted_l
kr=1;   % index for sub_sorted_r
k=1;    % index for result
while kl<=length(sub_sorted_l) && kr<=length(sub_sorted_r)
   if sub_sorted_l(kl)<sub_sorted_r(kr)   % ascending sort
       result(k)=sub_sorted_l(kl);   % result(k)
       kl=kl+1;
   else
       result(k)=sub_sorted_r(kr);
       kr=kr+1;
   end
   k=k+1;
end
% after one sub array is exhausted, put the rest of the other into the result
if kl>length(sub_sorted_l)
   for ki=0:(length(sub_sorted_r)-kr)
       result(k+ki)=sub_sorted_r(kr+ki);
   end
elseif kr>length(sub_sorted_r)
   for ki=0:(length(sub_sorted_l)-kl)
       result(k+ki)=sub_sorted_l(kl+ki);
   end
end
   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


运行示例:




merge_sort.m.zip




http://blog.sciencenet.cn/blog-71294-1042434.html

上一篇:[用MATLAB写算法]之排序算法1)插入排序
下一篇:Ubuntu 16.04上安装sentaurus TCAD遇到的问题及解决方法

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-4-9 05:12

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部