数据结构和算法

当前位置:首页>数据结构和算法

排序算法-归并排序

时间:2019-04-17   访问量:9

<?php

/**

 * 归并排序

 *

 * -------------------------------------------------------------

 * 思路分析:

 * 大O表示: O(n log n)

 * -------------------------------------------------------------

 * 比较a[i]和b[j]的大小,若a[i]≤b[j],则将第一个有序表中的元素a[i]复制到r[k]中,

 * 并令i和k分别加上1;否则将第二个有序表中的元素b[j]复制到r[k]中,并令j和k分别加上1,

 * 如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。

 * 归并排序的算法我们通常用递归实现,先把待排序区间[s,t]以中点二分,接着把左边子区间排序,再把右边子区间排序,

 * 最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]

 */

// +--------------------------------------------------------------------------

// | 解题方式

// +--------------------------------------------------------------------------

class MergeSort

{

    /**

     * MergeSort constructor.

     * 是开始递归函数的一个驱动函数

     *

     * @param array $arr 待排序的数组

     */

    public function __construct(array $arr)

    {

        $this->mSort($arr, 0, count($arr) - 1);

        var_dump($arr);

    }

    /**

     * 实际实现归并排序的程序

     *

     * @param $arr     array   需要排序的数组

     * @param $left    int     子序列的左下标值

     * @param $right   int     子序列的右下标值

     */

    public function mSort(&$arr, $left, $right)

    {

        if ($left < $right) {

            //说明子序列内存在多余1个的元素,那么需要拆分,分别排序,合并

            //计算拆分的位置,长度/2 去整

            $center = floor(($left + $right) / 2);

            //递归调用对左边进行再次排序:

            $this->mSort($arr, $left, $center);

            //递归调用对右边进行再次排序

            $this->mSort($arr, $center + 1, $right);

            //合并排序结果

            $this->mergeArray($arr, $left, $center, $right);

        }

    }

    /**

     * 将两个有序数组合并成一个有序数组

     *

     * @param &$arr   , 待排序的所有元素

     * @param $left   , 排序子数组A的开始下标

     * @param $center , 排序子数组A与排序子数组B的中间下标,也就是数组A的结束下标

     * @param $right  , 排序子数组B的结束下标(开始为$center+1)

     */

    public function mergeArray(&$arr, $left, $center, $right)

    {

        echo '| ' . $left . ' - ' . $center . ' - ' . $right . ' - ' . implode(',', $arr) . PHP_EOL;

        //设置两个起始位置标记

        $a_i  = $left;

        $b_i  = $center + 1;

        $temp = [];

        while ($a_i <= $center && $b_i <= $right) {

            //当数组A和数组B都没有越界时

            if ($arr[ $a_i ] < $arr[ $b_i ]) {

                $temp[] = $arr[ $a_i++ ];

            } else {

                $temp[] = $arr[ $b_i++ ];

            }

        }

        //判断 数组A内的元素是否都用完了,没有的话将其全部插入到C数组内:

        while ($a_i <= $center) {

            $temp[] = $arr[ $a_i++ ];

        }

        //判断 数组B内的元素是否都用完了,没有的话将其全部插入到C数组内:

        while ($b_i <= $right) {

            $temp[] = $arr[ $b_i++ ];

        }

        //将$arrC内排序好的部分,写入到$arr内:

        for ($i = 0, $len = count($temp); $i < $len; $i++) {

            $arr[ $left + $i ] = $temp[ $i ];

        }

    }

}

// +--------------------------------------------------------------------------

// | 方案测试

// +--------------------------------------------------------------------------

//do some test:

new mergeSort([4, 7, 6, 3, 9, 5, 8]);

/*

| 0 - 0 - 1 - 4,7,6,3,9,5,8

| 2 - 2 - 3 - 4,7,6,3,9,5,8

| 0 - 1 - 3 - 4,7,3,6,9,5,8

| 4 - 4 - 5 - 3,4,6,7,9,5,8

| 4 - 5 - 6 - 3,4,6,7,5,9,8

| 0 - 3 - 6 - 3,4,6,7,5,8,9

array(7) {

  [0] =>

  int(3)

  [1] =>

  int(4)

  [2] =>

  int(5)

  [3] =>

  int(6)

  [4] =>

  int(7)

  [5] =>

  int(8)

  [6] =>

  int(9)

}

 */


上一篇:排序算法-堆排序

下一篇:没有了!

在线咨询

点击这里给我发消息 售前咨询专员

点击这里给我发消息 售后服务专员

在线咨询

免费通话

24小时免费咨询

请输入您的联系电话,座机请加区号

免费通话

微信扫一扫

微信联系
返回顶部