image.png

圖中標(biāo)紅的下面代碼都有實(shí)現(xiàn)。

<?php

/**
 * 插入排序
 *     直接插入排序
 * 交換排序
 *      快排 冒泡
 * 選擇排序
 *      直接選擇
 * 歸并排序
 *      二路歸并
 * 基數(shù)排序
 */

//直接插入排序:
// 空間復(fù)雜度O(1)  時(shí)間復(fù)雜度O(n^2)  穩(wěn)定性：穩(wěn)定
function insertSort($arr)
{
    for ($i = 1, $l = count($arr); $i < $l; ++$i) {
        $tmp = $arr[$i];
        $j = $i - 1;
        while ($j >= 0 && $tmp < $arr[$j]) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        if (($j + 1) != $i) {
            $arr[$j + 1] = $tmp;
        }
    }
    return $arr;
}

//快速排序（交換排序）
//時(shí)間復(fù)雜度 O (nlogn)  不穩(wěn)定
function quickSort($arr)
{
    $l = count($arr);
    if ($l <= 1) return $arr;
    $base = $arr[0];
    $left = [];
    $right = [];
    for ($i = 1; $i < $l; ++$i) {
        if ($arr[$i] > $base) {
            $right[] = $arr[$i];
        } else {
            $left[] = $arr[$i];
        }
    }
    $right = quickSort($right);
    $left = quickSort($left);
    return array_merge($left, [$base], $right);
}


//冒泡排序（交換排序）
function bubble($arr)
{
    for ($i = 0, $l = count($arr); $i < $l - 1; $i++) {
        for ($j = 0; $j < $l - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $tmp;
            }
        }
    }
    return $arr;
}

//直接選擇排序（選擇排序 堆排序）
//時(shí)間復(fù)雜度 O（n）空間復(fù)雜度 O（1） 不穩(wěn)定
function selectSort($arr)
{
    for ($i = 0, $l = count($arr); $i < $l; ++$i) {
        $p = $i;
        for ($j = $i + 1; $j < $l; ++$j) {
            if ($arr[$j] < $arr[$p]) {
                $p = $j;
            }
        }
        if ($p != $i) {
            $tmp = $arr[$p];
            $arr[$p] = $arr[$i];
            $arr[$i] = $tmp;
        }
    }
    return $arr;
}

//歸并排序
//時(shí)間復(fù)雜度 O(nlogn) 穩(wěn)定
function mergeArray($arrA, $arrB)
{
    $a_i = $b_i = 0;
    $a_len = count($arrA);
    $b_len = count($arrB);
    while ($a_i < $a_len && $b_i < $b_len) {
        if ($arrA[$a_i] < $arrB[$b_i]) {
            $arrC[] = $arrA[$a_i++];
        } else {
            $arrC[] = $arrB[$b_i++];
        }
    }
    while ($a_i < $a_len) {
        $arrC[] = $arrA[$a_i++];
    }
    while ($b_i < $b_len) {
        $arrC[] = $arrB[$b_i++];
    }
    return $arrC;
}