php基础教程-数组归并排序算法[技术分享]

归并排序

归并排序(MERCE-SORT) 是建立在归并操作上的一种有效的排序算法，该算法是采用分治法(Divide and Conquer)的一一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列;即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成个有序表，称为二路归并。

归并排序的算法是：

1、将数组折分成两个数组

2、重复步骤1将数组拆分成最小单元

3、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

4、设定两个指针，最初位盟分别为两个已经排序序列的起始位置

5、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位

6、重复步骤3直到某-指针超出序列尾

7、将另一序列剩下的所有元素直接复制到合并序列尾

示例代码

示例地址：https://www.vqqc.cn/try/php/basics/merge_sort.php

<?php

// PHP数组排序算法：合并算法
// 二路归并
$arr1 = array(1,3,5);
$arr2 = array(2,4,6);

// 取出一个空数组用于归并空间
$arr3 = array();
while(count($arr1) && count($arr2)){
    // 只要$arr1和$arr2里面还有元素，就进行循环
    // 取出每个数组的第一个元素：进行比较
    $arr3[] = $arr1[0] < $arr2[0] ? array_shift($arr1) : array_shift($arr2);
}

// // 合并结果
// print_r(array_merge($arr3,$arr1,$arr2));

$arr = array(4,7,2,1,5,9,3);

// 归并排序函数
function merge_sort($arr){
    // 递归出口
    $len = count($arr);
    if($len <= 1) return $arr;
    
    // 拆分
    $middle = floor($len / 2);
    $left = array_slice($arr,0,$middle);
    $right = array_slice($arr,$middle);
    
    // 递归点：$left和$right都没有排好序：而且可能是多个元素的数组
    $left = merge_sort($left);
    $right = merge_sort($right);
    
    // 假设左边和右边都已经排好序；二路合并
    $m = array();
    while(count($left) && count($right)){
        // 只要$arr1和$arr2里面还有元素，就进行循环
        // 取出每个数组的第一个元素：进行比较
        $m[] = $left[0] < $right[0] ? array_shift($left) : array_shift($right);
    }
    // 返回结果
    return array_merge($m,$left,$right);
    
}

echo '<pre>';
print_r(merge_sort($arr));

返回结果

Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 7
    [6] => 9
)