然 后判断 $left 是否小于$right，如果小于，说明这个序列内元素个数大于一个，就将其拆分成两个数组，拆分的方式是生成一个中间的指示器$center，值 为$left + $right /2 整除。结果为：3，然后将$left 到$center 分成一组，$center+1到$right分成一组：
4 3 7 9
2 8 6
接下来，递归的 利用$left, $center, $center+1, $right分别做为 两个序列的 左右指示器，进行操作。知道数组内有一个元素$left==$right .然后按照上面的合并数组即可：
/** * mergeSort 归并排序 * 是开始递归函数的一个驱动函数 * @param &$arr array 待排序的数组 */ function mergeSort(&$arr) { $len = count($arr);//求得数组长度 mSort($arr, 0, $len-1); } /** * 实际实现归并排序的程序 * @param &$arr array 需要排序的数组 * @param $left int 子序列的左下标值 * @param $right int 子序列的右下标值 */ function mSort(&$arr, $left, $right) { if($left < $right) { //说明子序列内存在多余1个的元素，那么需要拆分，分别排序，合并 //计算拆分的位置，长度/2 去整 $center = floor(($left+$right) / 2); //递归调用对左边进行再次排序： mSort($arr, $left, $center); //递归调用对右边进行再次排序 mSort($arr, $center+1, $right); //合并排序结果 mergeArray($arr, $left, $center, $right); } } /** * 将两个有序数组合并成一个有序数组 * @param &$arr, 待排序的所有元素 * @param $left, 排序子数组A的开始下标 * @param $center, 排序子数组A与排序子数组B的中间下标，也就是数组A的结束下标 * @param $right, 排序子数组B的结束下标（开始为$center+1) */ function mergeArray(&$arr, $left, $center, $right) { //设置两个起始位置标记 $a_i = $left; $b_i = $center+1; while($a_i<=$center && $b_i<=$right) { //当数组A和数组B都没有越界时 if($arr[$a_i] < $arr[$b_i]) { $temp[] = $arr[$a_i++]; } else { $temp[] = $arr[$b_i++]; } } //判断 数组A内的元素是否都用完了，没有的话将其全部插入到C数组内： while($a_i <= $center) { $temp[] = $arr[$a_i++]; } //判断 数组B内的元素是否都用完了，没有的话将其全部插入到C数组内： while($b_i <= $right) { $temp[] = $arr[$b_i++]; } //将$arrC内排序好的部分，写入到$arr内： for($i=0, $len=count($temp); $i<$len; $i++) { $arr[$left+$i] = $temp[$i]; } } //do some test: $arr = array(4, 7, 6, 3, 9, 5, 8); mergeSort($arr); print_r($arr);
注意上面的代码带排序的数组都使用的是 引用传递，为了节约空间。
而且，其中的合并数组的方式也为了节约空间做了相对的修改，把所有的操作都放到了$arr上完成，引用传递节约资源。
好了 上面的代码就完成了归并排序，归并排序的时间复杂度为O(N*LogN) 效率还是相当客观的。
再说，归并排序算法，中心思想是 将一个复杂问题分解成相似的小问题，再把小问题分解成更小的问题，直到分解到可以马上求解为止，然后将分解得到的结果再合并起来的一种方法。这个思想用个 成语形容叫化整为零。 放到计算机科学中有个专业属于叫分治策略（分治发）。分就是大问题变小问题，治就是小结果合并成大结果。
分治策略是很多搞笑算法的基础，我们在讨论快速排序时，也会用到分治策略的。
最后简单的说一下这个算法，虽然这个算法在时间复杂度上达到了O(NLogN)。但是还是会有一个小问题，就是在合并两个数组时，如果数组的总元素个数为 N，那么我们需要再开辟一个同样大小的空间来保存合并时的数据（就是mergeArray中的$temp数组），而且还需要将数据有$temp拷贝 会$arr，因此会浪费一些资源。因此在实际的排序中还是 相对的较少使用。
您可能感兴趣的文章: