常见算法4、合并(归并)排序 Merge sort

一、简介

归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

二、算法原理：

假如如我这里有一组数据，归并排序过程如下：

通俗点来说，就是先分割，再合并。分割的过程中其实可理解为就是以二分法将数组分割成最小单元，然后再按顺序合并起来。

三、代码实现：

1、Python 3 ：

#分割
def merge_sort(arr):
    import math
    if len(arr) < 2:
        return arr
    else:
        middle = math.floor(len(arr)/2)
        pivot = arr[0]
        left, right = arr[0:middle], arr[middle:]
        return merge(merge_sort(left), merge_sort(right))
#合并
def merge(left,right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
    return result

myarr = [5,7,12,1,6,88,9,0]
print(merge_sort(myarr))

=============== 运行结果：===============
[0, 1, 5, 6, 7, 9, 12, 88]

2、PHP：

function merge_sort($arr){
    $length = count($arr);
    if($length<2){
        return $arr;
    }
    $middle = floor($length/2);
    $left = array_slice($arr, 0, $middle);
    $right = array_slice($arr, $middle);
    return merge(merge_sort($left), merge_sort($right));
}

function merge($left,$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;
}

$my_arr = [5, 3, 6, 2, 10,1,18];
print_r(merge_sort($my_arr)); 

=============== 运行结果：===============
Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 5 [4] => 6 [5] => 10 [6] => 18 )