php归并排序算法示例_PHP_编程开发_程序员俱乐部

class="php" name="code">
<?php
/**
 * php 归并排序算法示例。这是无指针型的，代码容易看懂。
 * 实际生产应用中，用指针速度更快。
 * 
 * 输出如下：
 * 
 * 
start : 0 end: 1 临时数组：array ( 0 => 30, 1 => 66, )
start : 2 end: 3 临时数组：array ( 0 => 6, 1 => 45, )
start : 0 end: 3 临时数组：array ( 0 => 6, 1 => 30, 2 => 45, 3 => 66, )
最终结果:array ( 0 => 6, 1 => 30, 2 => 45, 3 => 66, )
 * 
 * 
 * @author xieye
 */

$arr = [30, 66,   45,6,]; // 原始数组
$sort_arr =  merge_sort( $arr );  // 排序
echo  "最终结果:".var_export( $sort_arr, 1 ) ; //打印结果

// 归并算法总函数
function merge_sort ( array $arr )
{
    return  msort( $arr, 0, count( $arr ) - 1 );
}

// 递归分治，归并，此算法本身的思想是非常巧妙的。
function msort ( array $arr, $start, $end )
{
    // 当子序列长度为1时，$start == $end，不用再分组，直接返回。
    if ($start < $end) {
        $mid = floor( ( $start + $end ) / 2 ); // 将 $arr 平分为 $arr[$start - $mid] 和 $arr[$mid+1 - $end]
        $arr = msort( $arr, $start, $mid ); // 分治，将 $arr[$start - $mid] 归并为有序的$arr[$start - $mid]
        $arr = msort( $arr, $mid + 1, $end ); // 分治，将 $arr[$mid+1 - $end] 归并为有序的 $arr[$mid+1 - $end]

        $temparr = merge( $arr, $start, $mid, $end ); // 归并，将$arr[$start - $mid]部分和$arr[$mid+1 -end]部分合并起来成为有序的$arr[$start - $end]
        echo "start : {$start}  end: {$end} "." 临时数组：".  var_export( $temparr, 1 )."<br>";
        
        foreach ($temparr as $v) { // 将临时数组的值，也就是排序结果，替换掉原数组的对应位置。
            $arr[$start ++] = $v;
        }
    }
    return $arr;
}

// 单独的归并算法，不含分治。
// 前提是 start到mid部分是有序的，mid到end部分是有序的。所以合并的结果也是有序的。
// 归并算法的唯一缺点是，需要一块跟原数组一样大的内存空间。
function merge ( array $arr, $start, $mid, $end )
{
    $temparr = [];
    // 根据 下标 截取成两个数组。
    $arr_left = array_slice( $arr, $start, $mid - $start + 1 );
    $arr_right = array_slice( $arr, $mid + 1, $end - $mid );
    
    while ($arr_left || $arr_right) { // 只要left数组和right数组任何一个不空，请不停继续下去。
        if ($arr_left && $arr_right) { // 如果两个数组都有值，则取头部的最小值放到临时数组，并删除这个值在原数组中。
            if ($arr_left[0] < $arr_right[0]) {
                $temparr[] = array_shift( $arr_left ); // 弹出第一个并保存
            } else {
                $temparr[] = array_shift( $arr_right ); // 弹出第一个并保存，包括相等的情况。
            }
        } elseif (! $arr_left) { // 剩余两个else的存在意义：两个数组总有一方先取完，那就不需要比较了，于是取剩余的放到临时数组里。
            $temparr[] = array_shift( $arr_right );
        } else {
            $temparr[] = array_shift( $arr_left );
        }
    }
    return $temparr;
}