萬盛學電腦網

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

PHP 插入排序法實現陣列排序詳解

算法原理

插入排序 將陣列分為「已排序區」與「未排序區」。初始時已排序區只有第一個元素。每次從未排序區取出第一個元素,在已排序區中從右向左比較,找到適當位置插入,並將較大元素右移。重複直到未排序區為空。

逐步執行示意 (由大到小排序)

原始陣列:[2, 6, 3, 9]

  1. i=1:取 6,與 2 比較,6>2 → 插入索引 0 → [6, 2, 3, 9]
  2. i=2:取 3,與 2 比較 3>2 → 右移 2;與 6 比較 3<6 → 插入索引 1 → [6, 3, 2, 9]
  3. i=3:取 9,依序與 2、3、6 比較,皆小於 9 → 插入索引 0 → [9, 6, 3, 2]

PHP 實作 (參考傳遞,原地排序)

<?php
function insertSort(&$arr) {
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $insertVal = $arr[$i];
        $j = $i - 1;
        // 從右向左掃描已排序區
        while ($j >= 0 && $insertVal > $arr[$j]) { // 由大到小用 >
            $arr[$j + 1] = $arr[$j]; // 右移
            $j--;
        }
        $arr[$j + 1] = $insertVal; // 插入空位
    }
}

$myarr = array(2, 6, 3, 9);
insertSort($myarr);
echo '<pre>'; print_r($myarr); // [9, 6, 3, 2]
?>

複雜度分析

情況時間複雜度比較次數移動次數
最好 (已排序)O(n)n-10
最差 (逆序)O(n²)n(n-1)/2n(n-1)/2
平均O(n²)~n²/4~n²/4

適用場景與優化

  • 小規模資料 (n < 50):簡單高效,常作為快速排序、希爾排序的基礎情況。
  • 近乎有序資料:接近 O(n) 效能,極佳。
  • 優化方向:二分搜尋插入位置 (Binary Insertion Sort) 減少比較次數;希爾排序 (Shell Sort) 改善移動效率。
  • PHP 內建替代:實務上直接使用 rsort() (由大到小) 或 arsort() (保留鍵名),底層採用 Quicksort,效能遠優於純 PHP 實作。
copyright © 萬盛學電腦網 all rights reserved