数据结构和算法——合并排序

Lemon黄

发布于 2019-11-24 16:07:01

5750

发布于 2019-11-24 16:07:01

文章被收录于专栏：Lemon黄

1、要解决的问题

给定如下所示的数字列表，请按升序对它们进行排序。

$numbers = [21,25,100,98,89,77];

要求

对数字进行排序时，需要使用插入合并算法。
用PHP实现该算法

2、伪代码说明

合并排序是一种分而治之的算法。它的工作方式是将列表连续分成两半，直到两半都被排序，然后执行操作合并将两个列表组合成一个排序的新列表。

拆分列表时，如果列表包含零个或一个元素，我们认为该列表已排序。

拆分：

合并：

描述合并排序的伪代码如下：

PROCEDURE function mergeSort   FOR each element of the master list indexed by i        if ( i <= 1 ) return a        var left = a[0] to a[i/2]       var right = a[i/2+1] to a[i]        left = mergeSort( left )       right = mergeSort( right )        return merge( left,right )    END FOREND PROCEDURE PROCEDURE function mergeSort    WHILE length(left) > 0 and length(right) > 0        if first(left) â‰¤ first(right)            append first(left) to result            left = rest(left)        else            append first(right) to result            right = rest(right)     IF length(left) > 0        append left to result    END IF     IF length(right) > 0        append right to result    END IF     return resultEND PROCEDURE

3、PHP实现合并排序

我们可以看到，该算法有两个过程。这导致我们需要两个PHP函数，其中第一个函数（mergeSort）涉及递归。

<?php$arrayToSort = [21, 25, 100, 98, 89, 77]; function mergeSort($data){    if (count($data) <= 1) {        return $data;    }     $left = array_slice($data, 0, intval((count($data) / 2)));    $right = array_slice($data, intval(count($data) / 2));     $left = mergeSort($left);    $right = mergeSort($right);     return merge($left, $right);} function merge($left, $right){    $sorted = [];     while (count($left) > 0 && count($right) > 0) {        if ($left[0] < $right[0]) {            $firstLeft = array_shift($left);            $sorted[] = $firstLeft;        } else {            $firstRight = array_shift($right);            $sorted[] = $firstRight;        }    }     for ($i = 0; $i < count($left); $i++)        $sorted[] = $left[$i];     for ($i = 0; $i < count($right); $i++)        $sorted[] = $right[$i];     return $sorted;} print_r(mergeSort($arrayToSort)); // Output:/*Array(    [0] => 21    [1] => 25    [2] => 77    [3] => 89    [4] => 98    [5] => 100)*/

我们严格遵循伪代码并用PHP实现该算法。我们要强调的唯一部分是几个内置的PHP数组函数：