排序算法——归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

分而治之

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。

合并相邻有序子序列

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

JAVA版：

这是在网上看到的一个帖子，主要是图文部分让大家一看就能明白“归并算法”的要义，适合小白们学习，所以也扒来放到“菠菜园”上。下面我为大家再补充一个PHP版的。

<?php
class SortTest {
//归并主函数
public function merge_sort(array &$arr){
$start = 0;
$end = count($arr) - 1;
$this->mSort($arr,$start,$end);
}
private function msort(array &$arr,$start,$end){
if($start < $end){
//当子序列长度为1时，$start == $end，不用再分组
$mid = floor(($start + $end) / 2); //将 $arr 平分为 $arr[$start - $mid] 和 $arr[$mid+1 - $end]
$this->msort($arr,$start,$mid); //将 $arr[$start - $mid] 归并为有序的$arr[$start - $mid]
$this->msort($arr,$mid + 1,$end); //将 $arr[$mid+1 - $end] 归并为有序的 $arr[$mid+1 - $end]
$this->merge($arr,$start,$mid,$end); //将$arr[$start - $mid]部分和$arr[$mid+1 - $end]部分合并起来成为有序的$arr[$start - $end]
}
}
//归并操作
private function merge(array &$arr,$start,$mid,$end){
$i = $start;
$j=$mid + 1;
$k = $start;
$temparr = array();
while($i!=$mid+1 && $j!=$end+1){
if($arr[$i] >= $arr[$j]){
$temparr[$k++] = $arr[$j++];
}else{
$temparr[$k++] = $arr[$i++];
}
}
//将第一个子序列的剩余部分添加到已经排好序的 $temparr 数组中
while($i != $mid+1){
$temparr[$k++] = $arr[$i++];
}
//将第二个子序列的剩余部分添加到已经排好序的 $temparr 数组中
while($j != $end+1){
$temparr[$k++] = $arr[$j++];
}
for($i=$start; $i<=$end; $i++){
$arr[$i] = $temparr[$i];
}
}
}
?>