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