PHP实现归并排序算法的方法详解

归并排序算法简介

归并排序是一种使用分治法思想的高效稳定排序算法。其基本思想是将待排序的序列拆分成若干个子序列，对每个子序列进行排序，然后将排序后的子序列合并成一个大的有序序列。 归并排序算法的复杂度为O(nlogn)，适用于各种数据规模的排序。

归并排序算法步骤

1. 将序列递归拆分成若干个子序列。
2. 对每个子序列进行递归排序。
3. 将排序好的子序列合并成一个大的有序序列。

PHP实现归并排序算法

示例代码如下：

function merge_sort($arr){
    $len=count($arr);
    if($len<=1){
        return $arr;
    }
    $mid=intval($len/2);
    $left=array_slice($arr,0,$mid);
    $right=array_slice($arr,$mid);
    $left=merge_sort($left);
    $right=merge_sort($right);
    return merge($left,$right);
}

function merge($left,$right){
    $res=array();
    while(count($left)&&count($right)){
        if($left[0]<=$right[0]){
            $res[]=$left[0];
            $left=array_slice($left,1);
        }else{
            $res[]=$right[0];
            $right=array_slice($right,1);
        }
    }
    while(count($left)){
        $res[]=$left[0];
        $left=array_slice($left,1);
    }
    while(count($right)){
        $res[]=$right[0];
        $right=array_slice($right,1);
    }
    return $res;
}

此示例中，merge_sort()函数用来递归拆分序列并进行排序，merge()函数用来合并排序好的子序列。

示例说明

我们使用以下示例来说明归并排序算法的实现过程：

$arr = [3, 1, 4, 1, 5, 9, 2, 6];

$sorted_arr = merge_sort($arr);

print_r($sorted_arr);

输出结果为：

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

我们还可以使用更大的数据来测试算法的性能。以下是一个包含10000个随机数的数组的排序测试结果：

$arr = [];
for($i=0;$i<10000;$i++){
    $arr[] = mt_rand(0, 10000);
}

$start_time = microtime(true);

$sorted_arr = merge_sort($arr);

$end_time = microtime(true);

$total_time = $end_time - $start_time;

echo "Sorting time for array of 10000 items: ".$total_time." seconds\n";

输出结果为：Sorting time for array of 10000 items: 0.1058030128479 seconds。

可以看出，归并排序算法性能优秀，即使处理包含大量随机数的数组时也能迅速排序。