php实现 归并排序，快速排序

归并排序

归并排序采用分治，递归思想。先将数据从中间分开，分成两个部分。然后前后两部分分别排序（继续分，直至最后只有一个数），再合并，排序完成。

$array = [5,4,6,9,1,4,4,9];
function sortd($array){
    if (count($array)>1) {
        $num = count($array);
        $middle = floor($num/2);
        $arrLeft= array_slice($array, 0, $middle);
        $arrRight= array_slice($array, $middle);
        return merge(sortd($arrLeft), sortd($arrRight));
    } else {
        return $array;
    }
}

function merge($array1, $array2) {
    $newArray = [];
    $index1 = 0;
    $index2 = 0;
    $num1 = count($array1);
    $num2 = count($array2);
    while ($index1<$num1 && $index2<$num2) {
        $newArray[] = $array1[$index1]>$array2[$index2]?$array1[$index1++]:$array2[$index2++];
    }
    for ($index1; $index1<$num1; $index1++) {
        $newArray[] = $array1[$index1];
    }
    for ($index2; $index2<$num2; $index2++) {
        $newArray[] = $array2[$index2];
    }
    return $newArray;
}

快速排序

快速排序也是采用分治和递归思想；将数据找出一个数，将比小的放在一边，比他大的放在另一边这个数放中间。然后这两个区域重复上一步操作，直到两边的数剩下一个数，排序完成。

function quickSort($arr){
    $num = count($arr);
    if ($num <= 1) {
        return $arr;
    }
    $middle = $arr[0];
    $leftArray = array();
    $rightArray = array();

    for ($i = 1; $i < $num; $i++) {
        if ($arr[$i] < $middle) {
            $rightArray[] = $arr[$i];
        } else {
            $leftArray[] = $arr[$i];
        };
    }
    $leftArray = quickSort($leftArray);
    $leftArray[] = $middle;

    $rightArray = quickSort($rightArray);
    return array_merge($leftArray, $rightArray);
}

本作品采用《CC 协议》，转载必须注明作者和本文链接