PHP – 归并排序 – 老迟笔记

一、概述

1、原理

对于给定的一组记录（假设有 n 个记录），首先将数组一分为二，对于每个子数组采用同样的方法递归的划分为更小的数组，直到子数组的大小为1 （大小为 1 的子数组是有序的）。

接着需要把相邻的两个子数组进行归并（归并后的数组还是有序的）为更大的数组，直到归并后的数组大小和原来的数组大小相同，算法结束。

所以，归并排序的关键就是两步：第一步，划分子表；第二步，合并半子表。

　
2、处理过程

归并排序时利用递归和分治技术将数据序列划分成越来越小的子表，再对子集进行排序，最后用递归方法将排好序的子表合并成为越来越大的有序序列。

归并排序中，“归” 代表递归，即递归的将数组折半的分离为两个子数组，如数组[2, 6, 1, 0]，会先折半为 [2, 6] 和 [1, 0] 两个数组，然后再折半，将数组分离，分为 [2], [6], [1], [0]。

归并排序中，“并” 代表合并，即将分开的数组按照从小到大或者从大到小的顺序再放到一个数组中。如上面的 [2] 和 [6] 合并到一个数组中是 [2, 6]，然后再将 [1] 和 [0] 合并到一个数组中，是 [0, 1]，然后再将 [2, 6] 和 [0, 1] 合并到一个数组中即为 [0, 1, 2, 6]。

二、PHP代码实现

<?php
declare(strict_types = 1);

class TestCase
{
    /**
     * 归并排序
     *
     * @param array $array
     * @return array
     */
    public function sortArray(array $array) : array
    {
        // 采用自上而下的递归方法
        $arrayLen = count($array);
        if ($arrayLen < 2) {
            return $array;
        }
        // 中间元素的下标
        $middleSubscript = intval(floor($arrayLen / 2));
        // 以中间元素划分数组元素
        $left = array_slice($array, 0, $middleSubscript);
        $right = array_slice($array, $middleSubscript);
        return $this->mergeArray($this->sortArray($left), $this->sortArray($right));
    }


     /**
     * 归并排序合并数组函数
     *
     * @param array $left
     * @param array $right
     * @return array
     */
    public function mergeArray(array $left, array $right) : array
    {
        $result = [];
        while (true == count($left) && true == count($right)) {
            if ($left[0] <= $right[0]) {
                array_push($result, array_shift($left));
            } else {
                array_push($result, array_shift($right));
            }
        }

        while (true == count($left)) {
            array_push($result, array_shift($left));
        }
        while (true == count($right)) {
            array_push($result, array_shift($right));
        }
        return $result;
    }
}


// 需要排序数组
$arr = [20, 19, 15, 36, 22, 3, 77, 95, 64, 15, 24, 36];
// 执行排序
$arrObject = new TestCase();
$arr = $arrObject->sortArray($arr);
// 输出结果
foreach ($arr as $v) {
    echo $v . ' ';
}

// 结果
3 15 15 19 20 22 24 36 36 64 77 95

打赏赞