PHP数据结构(二十五)——并归排序
(原创内容,转载请注明来源,谢谢)
一、概述
并归排序是将两个或两个以上的有序表组合成一个新的有序表。采用并归的思想进行排序的方式如下:
假设初始序列含有n个记录,则看成是n个有序的子序列,每个子序列长度是1,然后两两合并,得到n/2个长度为2或者1(元素总数是奇数时,最后一个元素是单个的)的子序列。然后再进行归并,直至归并成一个数组。此方法也成为2-路并归排序。
二、算法
并归排序有两个核心——拆分、合并。
1)对于拆分,需要把数组拆成仅含一个元素的数组。
2)对于合并,两两合并的过程中再进行排序。
三、程序实现过程
1)获取数组,取数组长度的一半作为中间值,将数组分割成两部分。并用递归的方式将数组拆成更小的模块。直到数组都是一个元素。
2)将数组递归合并,边合并边进行比较,确保合并后的数组是从小到大排好序的数组,合并后返回给上一层。
四、并归排序图(图片来自网络)
五、实现源程序
//并归排序
publicfunction mergeSortArray(array $arr = array()){
if(empty($arr)){
$arr= $this->arr;
}
$arrLength= count($arr);
//长度只有1直接返回
if(1>= $arrLength){
return$arr;
}
//取中间值作为下标
$middle= floor($arrLength/2);
//分割出左数组,从0到中间
$arrLeft= array_slice($arr, 0, $middle);
//分割出右数组,从中间到最后
$arrRight= array_slice($arr, $middle, $arrLength-1);
//采用递归的方式进行分割
$arrLeft= $this->mergeSortArray($arrLeft);
$arrRight= $this->mergeSortArray($arrRight);
$arr= $this->_mergeSplitedArray($arrLeft, $arrRight);
return$arr;
}
//并归排序的私有方法,将两个数组有序合并
publicfunction _mergeSplitedArray(array $arrLeft, array $arrRight){
$arrRes= array();
$leftIndex= 0;
$rightIndex= 0;
//遍历数组,合成最终的数组
while($leftIndex< count($arrLeft) && $rightIndex < count($arrRight)){
//如果左边小,则取左边的值,并把左边的下标加一。否则取右边的值,并把右边的下标加一。
$arrRes[]= $arrLeft[$leftIndex] < $arrRight[$rightIndex] ? $arrLeft[$leftIndex++] :$arrRight[$rightIndex++];
}
//将其中一边数组剩余的结果合并进来,下面两个while会执行其中一个
while($leftIndex< count($arrLeft)){
$arrRes[]= $arrLeft[$leftIndex++];
}
while($rightIndex< count($arrRight)){
$arrRes[]= $arrRight[$rightIndex++];
}
return$arrRes;
}
——written by linhxx 2017.07.20
相关阅读: