算法系列-归并排序

phpman.song@gmail.com发布

定义

归并排序是用来排列一连串数字的算法

原理

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  4. 重复步骤3直到某一指针达到序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

PHP实现

PHP沙盒环境

function mergeSort($arr)
{
    $len = count($arr);
    if ($len < 2) {
        return $arr;
    }
    $middle = floor($len / 2);
    $left = array_slice($arr, 0, $middle);
    $right = array_slice($arr, $middle);
    return merge(mergeSort($left), mergeSort($right));
}

function merge($left, $right)
{
    $result = [];

    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] <= $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }

    while (count($left))
        $result[] = array_shift($left);

    while (count($right))
        $result[] = array_shift($right);

    return $result;
}

//例子
$numbers = [1,3,4,22,88,33,31,42];
print_r(mergeSort($numbers));


分类: 算法

17 条评论

levitra buy · 2021年1月8日 上午5:11

I wanted to send you the very little remark to finally thank you the moment again over the remarkable tactics you have shared on this page. This has been simply surprisingly open-handed with you to offer unhampered what most of us would’ve offered for sale for an ebook to help make some money on their own, precisely seeing that you might have tried it in case you desired. Those suggestions in addition worked to become good way to realize that some people have the identical keenness similar to my personal own to realize significantly more when it comes to this matter. I believe there are several more pleasant sessions up front for people who scan your site.

cialis cialis · 2021年1月8日 上午6:03

I am glad for writing to make you know what a incredible encounter my friend’s girl gained studying your web page. She learned plenty of pieces, which include what it’s like to possess an awesome helping mood to let other folks smoothly know just exactly several multifaceted subject matter. You truly exceeded our own expectations. Thank you for offering these necessary, safe, explanatory and even fun tips about this topic to Julie.

bupron tablets · 2021年1月8日 上午10:21

Thanks for your whole work on this website. My niece takes pleasure in working on research and it is simple to grasp why. We all notice all relating to the powerful ways you render vital tricks via your website and therefore welcome response from website visitors on this topic while our own simple princess is without question understanding so much. Take pleasure in the rest of the year. Your performing a wonderful job.

ARIPIPRAZOLE · 2021年1月8日 上午10:26

I am just writing to make you understand what a perfect experience my wife’s princess obtained using your webblog. She came to understand a lot of issues, not to mention what it’s like to have an amazing giving mood to have most people really easily know selected impossible subject areas. You really exceeded our own expectations. Many thanks for imparting the interesting, safe, explanatory and even easy thoughts on the topic to Janet.

generic abilify · 2021年1月8日 上午10:28

I precisely desired to say thanks again. I’m not certain the things I could possibly have achieved in the absence of the concepts contributed by you about my area of interest. Entirely was a daunting circumstance for me, but coming across a expert avenue you dealt with it forced me to cry for contentment. Extremely grateful for the advice and expect you are aware of a powerful job that you are accomplishing educating many people all through a site. I’m certain you’ve never come across all of us.

发表评论

邮箱地址不会被公开。 必填项已用*标注