10大经典排序算法之归并排序(PHP版)

发布时间:2020/11/20 作者:天马行空 阅读(1122)

归并排序,是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。核心思想是将两个已经排序好的序列,合并成一个排序的序列。


算法步骤
1、以递归的方式将一个数组从中间拆分成两个子数组,一直拆分下去,直到子数组中值剩下一个元素为止;
2、分别从两个子数组的开头取值进行比较,小(大)的放入一个新数组,并且继续下一轮比较,直到其中一个数组中的值被取光为止;
3、然后把还没有取完的值的子数组取出来放到新数组的最后;
4、将新的有序数组替换到原数组相应的位置上去。


动图演示

mergeSort.gif


代码实现:

public function mergeSort(array $arr)
{
    $len = count($arr);
    if ($len < 2) {
        return $arr;
    }
    $middle = floor($len / 2); // 将数组一分为二
    $left = array_slice($arr, 0, $middle);
    $right = array_slice($arr, $middle);
    
    return $this->merge($this->guibing($left), $this->guibing($right)); // 将已经一分为二的数组继续一分为二,直到每个子数组中都只有一个值,然后通过比较+合并返回新数组给
}

//合并两个有序数组
private function merge(array $left, array $right)
{
    $result = [];
    
    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] <= $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }
    
    while (count($left)) { // 将左边子数组中还没有取完的值,取出来放到新数组中
        $result[] = array_shift($left);
    }
    
    while (count($right)) { // 将右边子数组还没有取完的值,取出来放到新数组中
        $result[] = array_shift($right);
    }
    
    return $result;
}



关键字php 算法