PHP数据结构（二十五） ——并归排序

用户1327360

发布于 2018-03-07 11:07:49

1.5K0

发布于 2018-03-07 11:07:49

文章被收录于专栏：决胜机器学习决胜机器学习

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

相关阅读：