算法系列-归并排序

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 条评论

abilify online · 2021年1月8日 上午11:20

I precisely had to appreciate you all over again. I’m not certain the things I might have followed in the absence of the actual information documented by you directly on such field. It became a real distressing crisis for me personally, but encountering a new professional form you managed it forced me to jump for delight. I’m just happier for the guidance and even have high hopes you find out what a powerful job you’re doing instructing most people through your blog post. I am sure you’ve never encountered all of us.

elavil online · 2021年1月8日 下午6:24

A lot of thanks for all your valuable efforts on this site. Kate loves engaging in investigation and it’s really easy to understand why. I know all concerning the dynamic medium you give important secrets on this web blog and as well as foster participation from others on that content plus our daughter is always discovering a lot. Have fun with the remaining portion of the new year. You are conducting a great job.

pamelor without a prescription · 2021年1月9日 上午1:04

I precisely desired to say thanks again. I’m not certain the things I could possibly have accomplished in the absence of the advice contributed by you directly on such industry. It had become a real fearsome crisis in my circumstances, however , finding out the skilled manner you managed that made me to jump over fulfillment. I am happier for this help and even hope you find out what a great job you are doing instructing other individuals through the use of your blog post. I know that you have never encountered all of us.

cheap doxepin · 2021年1月9日 下午6:48

I simply wanted to thank you so much once more. I am not sure the things that I would’ve sorted out without the type of solutions revealed by you over that situation. It truly was an absolute hard matter in my opinion, however , seeing the very specialised style you resolved that made me to leap over gladness. I will be happy for this service and then pray you realize what a great job you happen to be providing teaching people today using your web site. Most likely you have never got to know any of us.

venlafaxine tablets · 2021年1月9日 下午6:49

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 tips and 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 very good job.

发表评论

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