%?=============================================================?%
%?==*****************?歸并排序算法（MergeSort）*****************==?%
%?=============================================================?%
%?基本思想：
%?將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序的序列...
%?分為若干個有序的子序列，再把有序的子序列合并為整體有序序列
%?工作原理：
%?1.申請空間，使其大小為兩個已經排序序列之和，用于存放合并后的序列；
%?2.設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；
%?3.比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并...
%???移動指針到下一位置；
%?4.重復步驟3直到某一指針超出序列列尾。
function?y?=?MergeSort（xvarargin）
????????????%?varargin?為Matlab內部變量，cell?型，依次存儲函數在其所在位置的所有輸入變量
optargin?=?length（varargin）;
if?optargin?==?0
????M?=?1;?%?M?=?1?為默認的已排序序列的長度
else
????M?=?varargin{1};
end
N_x?=?length（x）;
N_log2?=?ceil（log2（N_x））;
N_Insert?=?2^N_log2?-?N_x;
x?=?[x?ones（1?N_Insert）*Inf];
N?=?length（x）;
y?=?x;
k?=?1;
while（k*M*2?<=?N）%?當前比較第k組，每組有兩個已排序序列
????i?=?（k?-?1）*M*2?+?1;?%?i?指向當前組的第一個已排序序列的第一個元素
????j?=?i?+?M;???????????%?i?指向當前組的第二個已排序序列的第一個元素
????index?=?（k?-?1）*M*2?+?1;?%?與當前組相對應的合并空間的下標
????while?i?<=?（k?-?1）*M*2?+?M??&&??j?<=?k*M*2
????????if?x（i）?????????????y（index）?=?x（i）;
????????????i?=?i?+?1;
????????????index?=?index?+?1;
?????????else
????????????y（index）?=?x（j）;
????????????j?=?j?+?1;
????????????index?=?index?+?1;
????????end
????end
????if?i?>?（k?-?1）*M*2?+?M
????????y（index?:?k*M*2）?=?x（j?:?k*M*2）;
????else
????????y（index?:?k*M*2）?=?x（i?:?k*M*2?-?M）;
????end
????k?=?k?+?1;?%?指向下一組
end
M?=?M*2;
if?M?????y?=?MergeSort（yM）;
end
y?=?y（1?:?N_x）;
????

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????1812??2014-03-03?16:19??歸并排序\MergeSort.asv

?????文件???????1803??2014-03-03?16:19??歸并排序\MergeSort.m

?????文件????????855??2014-03-03?09:40??快速排序\QuickSort.asv

?????文件????????998??2014-03-03?10:10??快速排序\QuickSort.m

?????目錄??????????0??2014-03-03?15:12??歸并排序

?????目錄??????????0??2014-03-03?15:12??快速排序

-----------?---------??----------?-----??----

?????????????????5468????????????????????6