排序算法---归并排序

归并排序是一种稳定的排序算法。
归并操作的算法原理如下：
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));

排序算法---归并排序

原文：https://www.cnblogs.com/xinxinmifan/p/sort-algorithm-merge-sort.html