萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> Android 開發

PHP 四大經典排序算法實現:冒泡、選擇、插入、快速排序代碼詳解

算法是程序靈魂:PHP 開發者的必修課

雖業務開發常調用內建 sort(),但理解底層排序邏輯是進階高手的分水嶺。以數組 [1,43,54,62,21,66,32,78,36,76,39] 為例,解析四大經典算法 PHP 實現。

1. 冒泡排序:大數下沉,小數上浮

雙層循環,相鄰比較交換。外層控制輪數,內層遞減比較次數。時間複雜度 O(n²),教學價值大於實戰。

function bubbleSort($arr) {
    $len = count($arr);
    for ($i=1; $i<$len; $i++) {
        for ($k=0; $k<$len-$i; $k++) {
            if ($arr[$k] > $arr[$k+1]) {
                $tmp = $arr[$k+1];
                $arr[$k+1] = $arr[$k];
                $arr[$k] = $tmp;
            }
        }
    }
    return $arr;
}

2. 選擇排序:每輪挑最小換到前

外層鎖定位置,內層掃描未排區間最小值索引 $p,最後交換。同 O(n²),但交換次數少於冒泡。

function selectSort($arr) {
    $len = count($arr);
    for ($i=0; $i<$len-1; $i++) {
        $p = $i;
        for ($j=$i+1; $j<$len; $j++) {
            if ($arr[$p] > $arr[$j]) $p = $j;
        }
        if ($p != $i) {
            $tmp = $arr[$p]; $arr[$p] = $arr[$i]; $arr[$i] = $tmp;
        }
    }
    return $arr;
}

3. 插入排序:構建有序區,新元素插入合適位置

假設前 $i-1$ 有序,將 $arr[i]$ 向前比較移位插入。近乎有序數據下接近 O(n),實際工程常用於小規模或部分有序場景。

function insertSort($arr) {
    $len = count($arr);
    for ($i=1; $i<$len; $i++) {
        $tmp = $arr[$i];
        for ($j=$i-1; $j>=0; $j--) {
            if ($tmp < $arr[$j]) {
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $tmp;
            } else break;
        }
    }
    return $arr;
}

4. 快速排序:分治法巅峰,平均 O(n log n)

選基準(首元素),分區為左(小)右(大),遞歸排序左右再合併。PHP 遞歸實現簡潔,但大數據量注意棧溢出。

function quickSort($arr) {
    $len = count($arr);
    if ($len <= 1) return $arr;
    $base = $arr[0];
    $left = $right = [];
    for ($i=1; $i<$len; $i++) {
        if ($base > $arr[$i]) $left[] = $arr[$i];
        else $right[] = $arr[$i];
    }
    return array_merge(quickSort($left), [$base], quickSort($right));
}
排序算法

工程建議:生產環境直接用 sort()/usort()(C 實現的快速排序變體)。理解算法是為了面試、嵌入式受限環境、或自定義複雜比較邏輯時能夠自主實現。

copyright © 萬盛學電腦網 all rights reserved