算法系列-归并排序

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

kia key fob replacement · 2021年1月5日 上午5:47

Wohh just what I was searching for, appreciate it for posting.

fiat 500 replacement key · 2021年1月5日 上午9:18

Perfect piece of work you have done, this internet site is really cool with fantastic information.

buy cbd oil · 2021年1月7日 上午11:48

I needed to draft you one little observation so as to say thank you as before for those great knowledge you’ve documented here. It has been certainly pretty generous of people like you to convey freely exactly what a number of people could possibly have made available as an e book to earn some cash for their own end, even more so considering the fact that you could possibly have done it if you ever decided. The ideas also acted like a fantastic way to comprehend other individuals have similar dreams like my own to grasp good deal more on the subject of this issue. I’m sure there are many more fun occasions ahead for individuals that look into your blog post.

cbd oil · 2021年1月7日 下午12:15

I needed to create you one little observation just to say thank you as before for these fantastic information you’ve discussed here. It has been certainly particularly generous of people like you to convey freely all that a lot of people could possibly have made available as an e book to earn some cash for their own end, especially considering the fact that you could possibly have done it if you ever decided. The good tips also acted like a fantastic way to be sure that other individuals have similar dreams just like my own to grasp a whole lot more in terms of this issue. I’m sure there are many more fun occasions ahead for individuals that find out your blog post.

viagra tablets · 2021年1月8日 上午12:31

I wanted to post you that tiny remark to say thanks a lot over again just for the nice secrets you have featured in this case. It was really seriously open-handed with you to provide unreservedly what exactly numerous people would have sold for an electronic book to help with making some profit on their own, principally since you might well have tried it in the event you wanted. Those things likewise worked to become a great way to recognize that someone else have the same passion the same as my very own to see very much more with regard to this problem. I know there are some more pleasurable situations up front for those who start reading your website.

发表评论

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