归并排序是一种稳定的排序算法。
归并操作的算法原理如下：
1.均分数列为两个子数列
2.递归重复上一步骤，直到子数列只有一个元素
3.父数列合并两个子数列并进行比较排序，递归返回数列
数据演示： 待排序数列：26 55 1 91 0 18 8 20 3
均分数列：
[26 55 1 91] | [0 18 8 20 3]
[26 55] [1 91] | [0 18] [8 20 3]
[26] [55] [1] [91] | [0] [18] [8 20] [3]
[26] [55] [1] [91] | [0] [18] [8] [20] [3] //子序列只剩1个元素
[26 55] [1 91] | [0 18] [8 20] [3] //两两比较
[1 26 55 91] | [0 8 18 20] [3]
[1 26 55 91] | [0 3 8 18 20]
[0 1 3 8 18 20 26 55 91]
代码实现：
function mergeSort($arr) {
$len = count($arr);
if($len<=1) { //得到最小单元数组
return $arr;
}
$middle =floor($len/2);
$larr = array_slice($arr,0,$middle);
$rarr = array_slice($arr,$middle); //array_slice():从数组中取出一段
$left = mergeSort($larr);
$right = mergeSort($rarr);
return merge($left,$right);
}
function merge($left,$right) {
$sortArr = [];
while(count($left) && count($right)) {
if($left[0]>$right[0]) {
$sortArr[] = array_shift($right); //array_shift():将数组开头的单元移出数组
}else{
$sortArr[] = array_shift($left);
}
}
//左边序列或者右边序列有剩余元素
return array_merge($sortArr,$left,$right); //array_merge():合并一个或多个数组
}
print_r(mergeSort($arr));