归并排序

归并排序的实现分为 递归实现 与 非递归(迭代)实现。

• 递归实现是算法设计中分治策略的典型应用，将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。
• 非递归(迭代)实现首先进行是两两归并，然后四四归并，然后是八八归并，一直下去直到归并了整个数组。

1. 递归实现算法描述

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 然后把两个子序列递归的分成两个子序列，直到子序列元素个数为1；
• 将分好的子序列，两两结合，排序且合并；
• 递归的进行第三步直到所有的子序列合并成一个序列；

2. 递归实现的代码展示

/**
 * merge函数将指定的两个有序数组(arr1,arr2)合并并且排序
 * @param $arrA
 * @param $arrB
 * @return array
 */
function arr_merge($arrA, $arrB)
{
    $arrC = array();
    while(count($arrA) && count($arrB)){
        /**
         * 这里不断的判断哪个值小,就将小的值给到 arrC,但是 arrA 和 arrB 两个数组元素的个数可能不相等，
         * 就可能要剩下几个值,所以要将剩下的元素 merge 进 arrC 数组中
         */
        $arrC[] = $arrA['0'] < $arrB['0'] ? array_shift($arrA) : array_shift($arrB);
    }
    return array_merge($arrC, $arrA, $arrB);
}

/**
 * 递归实现归并排序
 * @param $arr
 * @return array
 */
function merge_sort1($arr){
    $len = count($arr);
    if($len <= 1){
        //递归结束条件
        return $arr;
    }

    //数组中间
    $mid = ceil($len/2);
    //拆分数组0-mid这部分给左边left_arr
    $arr_left = array_slice($arr, 0, $mid);
    //拆分数组mid-末尾这部分给右边right_arr
    $arr_right = array_slice($arr, $mid);
    //左边拆分完后开始递归合并往上走
    $left_arr = merge_sort1($arr_left);
    //右边拆分完毕开始递归往上走
    $right_arr = merge_sort1($arr_right);
    //合并两个数组,继续递归
    $arr = arr_merge($left_arr, $right_arr);

    return $arr;
}

$arr = array( 6, 4, 7, 2, 9, 8, 1 );
$arr_merge = array_merge($arr);

3. 递归实现动图演示

image

4. 非递归(迭代)实现算法描述

• 非递归(迭代)实现的归并排序(自底向上)，子数组的大小i初始为1，每轮翻倍
• 将分好的子序列，两两结合，排序且合并；
• 改变子数组的大小，重复第二步才做，直到所有的子序列合并成一个序列；

5. 非递归(迭代)实现代码展示

/**
 * merge函数将指定的两个有序数组(arr1,arr2)合并并且排序
 * @param $arrA
 * @param $arrB
 * @return array
 */
function arr_merge($arrA, $arrB)
{
    $arrC = array();
    while(count($arrA) && count($arrB)){
        /**
         * 这里不断的判断哪个值小,就将小的值给到 arrC,但是 arrA 和 arrB 两个数组元素的个数可能不相等，
         * 就可能要剩下几个值,所以要将剩下的元素 merge 进 arrC 数组中
         */
        $arrC[] = $arrA['0'] < $arrB['0'] ? array_shift($arrA) : array_shift($arrB);
    }
    return array_merge($arrC, $arrA, $arrB);
}

/**
 * 数组替换
 * @param $arr
 * @param $place_arr
 * @param $left
 * @return array
 */
function arr_replace($arr, $place_arr, $left){
    foreach ($place_arr as $place){
        $arr[$left] = $place;
        $left++;
    }

    return $arr;
}

/**
 * 非递归实现归并排序
 * @param $arr
 * @return array
 */
function merge_sort2($arr){
    $len = count($arr);

    $tmp_arr = array();
    for ($i=1; $i<=ceil($len/2); $i=$i*2){
        $left = 0;
        while (($left+$i) < $len){
            $right = $left+$i;
            $left_arr = array_slice($arr, $left, $i);
            $right_arr = array_slice($arr, $right, $i);
            $tmp_arr = arr_merge($left_arr, $right_arr);
            $arr = arr_replace($arr, $tmp_arr, $left);
            $left = $right+$i;
        }
    }

    return $arr;
}

6. 非递归实现动图演示

image