算法系列-归并排序

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

wellbutrin buy · 2021年1月10日 上午8:29

I’m just commenting to let you be aware of of the exceptional discovery my cousin’s daughter enjoyed going through your blog. She discovered lots of issues, most notably how it is like to have a very effective giving heart to have many more effortlessly fully understand certain extremely tough matters. You really did more than my desires. Many thanks for displaying the helpful, healthy, educational and also easy thoughts on the topic to Gloria.

doxepin cheap · 2021年1月10日 上午9:31

I simply wanted to thank you so much once more. I do not know what I would’ve sorted out without these strategies revealed by you over that subject. It was an absolute horrifying matter in my position, nevertheless spending time with this specialized style you resolved the issue took me to leap with happiness. I will be happy for your service and then sincerely hope you realize what an amazing job you have been providing teaching some other people using your web site. Most likely you haven’t got to know any of us.

发表评论

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