Matlab一段时间不用发现有些生疏了,就用归并排序来练手吧.代码没啥说的,百度有很多.写篇博客,主要是记下matlab语法,以后备查.
测试代码
|
srcData = [1,3,2,4,6,5,8,7,9]; %测试数据
dataSrcLength = length(srcData); %数据长度
srcData2 = diGuiMerge(srcData, 1,dataSrcLength) %递归实现 srcData1 = dieDaiMerge(srcData) %迭代实现 |
合并自函数M文件
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 说明：负责进行数据合并 % 参数： % dataSrc 待处理的数据 % left1 数据1的开始位置 % right1 数据1的结束位置 % left2 数据2的开始位置 % right2 数据2的结束位置 % 返回：合并后的数据 dataSrc %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function dataSrc = mergeSub(dataSrc, left1, right1, left2, right2)
dataSrcLength = length(dataSrc); tempData = zeros(1, right2 – left1 + 1); i = left1; j = left2; tempIndex = 1;
%进行数据合并 while(1) if dataSrc(i) >= dataSrc(j) tempData(tempIndex) = dataSrc(i); i = i+1; tempIndex = tempIndex + 1; else tempData(tempIndex) = dataSrc(j); j = j + 1; tempIndex = tempIndex + 1; end
if i > right1 || i > dataSrcLength break; end
if j > right2 || j > dataSrcLength break; end end
%查看左边数据是否还有剩下 while(i <= right1 && i <= dataSrcLength) tempData(tempIndex) = dataSrc(i); i = i + 1; tempIndex = tempIndex + 1; end
%查看右边数据是否还有剩下 while(j <= right2 && j <= dataSrcLength) tempData(tempIndex) = dataSrc(j); j = j + 1; tempIndex = tempIndex + 1; end
%把数据放回在原始数据中 j = 1; for i = left1: right2 dataSrc(i) = tempData(j); j = j + 1;
if j > right2 – left1 + 1 break; end
if j > dataSrcLength break; end end end |
递归实现M文件
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 说明：归并排序的递归实现 % 参数： % dataSrc 待处理的数据 % startIndex 数据的开始位置 % endIndex 数据的结束位置 % 返回：排序后的数据 dataSrc %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function srcData = diGuiMerge(srcData, startIndex, endIndex)
%待排序的数据只有一个,则直接返回 if endIndex – startIndex == 0 return; end
%归并排序左半边数据 srcData = diGuiMerge(srcData, 1, floor((startIndex + endIndex) / 2)); %归并排序右半边数据 srcData = diGuiMerge(srcData, floor((startIndex + endIndex) / 2) + 1, endIndex); %将两块数据合并 srcData = mergeSub(srcData, 1, floor((startIndex + endIndex) / 2), floor((startIndex + endIndex) / 2) + 1, endIndex);
end |
迭代实现M文件
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 说明：归并排序的迭代实现 % 参数： % dataSrc 待处理的数据 % 返回：排序后的数据 dataSrc %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function srcData = dieDaiMerge(srcData)
dataSrcLength = length(srcData); %数据长度
lengthStep = 1; %初始子排序长度
while(1)
%分步排序 srcData = merge2Sub(srcData, lengthStep);
if lengthStep * 2 > dataSrcLength break; end
lengthStep = lengthStep*2; end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 说明：归并排序的迭代实现的子函数 % 参数： % dataSrc 待处理的数据 % lengthStep 数据块长度 % 返回：排序后的数据 dataSrc %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function dataSrc = merge2Sub(dataSrc, lengthStep) dataSrcLength = length(dataSrc);
startIndex = 1; startIndexEnd = startIndex + lengthStep – 1; start2Index = startIndex + lengthStep; start2IndexEnd = start2Index + lengthStep – 1;
%合并指定长度的数据块 while(1) dataSrc = mergeSub(dataSrc, startIndex, startIndexEnd, start2Index, start2IndexEnd);
startIndex = start2Index + lengthStep; startIndexEnd = startIndex + lengthStep – 1; start2Index = startIndex + lengthStep; start2IndexEnd = start2Index + lengthStep – 1;
if startIndex > dataSrcLength || start2Index > dataSrcLength break; end end end |
