php - 请讲解该排序

Question

请详细讲解一下递归的过程
function al_merge($arrA,$arrB){

    $arrC = array();
    while(count($arrA)&&count($arrB)){
        $arrC[]=$arrA['0']<$arrB['0']?array_shift($arrA):array_shift($arrB);
    }
        return array_merge($arrC,$arrA,$arrB);
}

function al_merge_sort($arr){

    $len = count($arr);
    if($len<=1)
        return $arr;

    $mid = intval($len/2);
    $left_arr = array_slice($arr,0,$mid);
    $right_arr = array_slice($arr,$mid);
    $left_arr = al_merge_sort($left_arr);
    $right_arr = al_merge_sort($right_arr);
    $arr = al_merge($left_arr,$right_arr);
    return $arr;
}

$arr=array(5,7,8,3);
print_r(al_merge_sort($arr));

Answer 1

唉各位downvote的大真的也不要太急躁. 这样说吧, 题主桑你主要有3个问题:

• 看到你profile里的很多问题其实只需要仔细调试一下能解决, 不必特意提一个问题.
• 没有善用搜索引擎. 程序员都很喜欢分享知识, 所以无论是讲解什么语法,算法还是库的博客都非常多.
• 这种问题最好在sf的子站101里面提问. 说到sf, 建议善用一下markdown排版.

回到这个问题上面, 这种排序叫做归并排序, 算法思路叫分治法. 这个你在搜索引擎上随便动动手指就可以找到大量资料.

1. 首先是将$arr劈开成,两个数组$left_arr, $right_arr.
2. 然后将这些数组都分别再调用一次al_merge_sort(), 在这不停地调用过程中, 整个数组被不停地劈开, 再劈开.
3. 这么劈下去始终有一天数组会只剩下一个元素的. 一个元素就无需排序了, 直接返回.
4. 这时, 我们希望从al_merge_sort返回的都是已经排好序的数组了.
5. 然后调用al_merge(), 让它从小到大将两个已经排好序的数组从小到大混在一起.
6. 这样, 形成了一个新的排好序的数组, 好, 返回. 返回上去之后重复第四步.
7. 一直冒到最顶, 也就是你的代码最后一行所调用, 也是一个排好序的数组了.