PHP 經典排序算法大全：冒泡/歸並/快速/選擇/插入/二分查找

PHP 經典排序算法大全：冒泡/歸並/快速/選擇/插入/二分查找

排序與查找是程式設計基礎功力。本文整理 7 種經典算法的 PHP 實作，附上時間複雜度、穩定性分析與適用場景，適合面試複習與教學參考。

算法複雜度總覽

1. 冒泡排序

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

2. 選擇排序

function select_sort($arr) {
  $n = count($arr);
  for ($i = 0; $i < $n; $i++) {
    $k = $i;
    for ($j = $i + 1; $j < $n; $j++) {
      if ($arr[$j] < $arr[$k]) $k = $j;
    }
    if ($k != $i) {
      $tmp = $arr[$i];
      $arr[$i] = $arr[$k];
      $arr[$k] = $tmp;
    }
  }
  return $arr;
}

3. 插入排序

function insert_sort($arr) {
  $n = count($arr);
  for ($i = 1; $i < $n; $i++) {
    $tmp = $arr[$i];
    $j = $i - 1;
    while ($j >= 0 && $arr[$j] > $tmp) {
      $arr[$j + 1] = $arr[$j];
      $j--;
    }
    $arr[$j + 1] = $tmp;
  }
  return $arr;
}

4. 快速排序（遞歸分治）

function quick_sort($arr) {
  $n = count($arr);
  if ($n <= 1) return $arr;
  
  $pivot = $arr[0];
  $left = $right = array();
  
  for ($i = 1; $i < $n; $i++) {
    if ($arr[$i] <= $pivot) $left[] = $arr[$i];
    else $right[] = $arr[$i];
  }
  
  return array_merge(quick_sort($left), array($pivot), quick_sort($right));
}

5. 歸並排序（分治 + 合併）

function merge($left, $right) {
  $result = array();
  while (count($left) && count($right)) {
    $result[] = $left[0] < $right[0] ? array_shift($left) : array_shift($right);
  }
  return array_merge($result, $left, $right);
}

function merge_sort($arr) {
  $len = count($arr);
  if ($len <= 1) return $arr;
  
  $mid = intval($len / 2);
  $left = merge_sort(array_slice($arr, 0, $mid));
  $right = merge_sort(array_slice($arr, $mid));
  
  return merge($left, $right);
}

6. 二分查找（遞歸版）

function bin_search_recursive($arr, $low, $high, $target) {
  if ($low > $high) return false;
  $mid = intval(($low + $high) / 2);
  if ($arr[$mid] == $target) return $mid;
  return $target < $arr[$mid] 
    ? bin_search_recursive($arr, $low, $mid - 1, $target)
    : bin_search_recursive($arr, $mid + 1, $high, $target);
}

7. 二分查找（迭代版，推薦）

function bin_search_iterative($arr, $target) {
  $low = 0;
  $high = count($arr) - 1;
  
  while ($low <= $high) {
    $mid = intval(($low + $high) / 2);
    if ($arr[$mid] == $target) return $mid;
    if ($target < $arr[$mid]) $high = $mid - 1;
    else $low = $mid + 1;
  }
  return false;
}

PHP 內建排序函數（生產環境首選）

實務建議

• 生產代碼直接用內建函數：C 實作、高度優化、處理邊界情況完善
• 自定義比較用 usort/uasort：多欄位排序、對象屬性排序
• 大數據量外部排序：分塊排序 + 歸並合併（MapReduce 思想）
• 近乎有序數據：插入排序 O(n) 級表現
• 面試手寫重點：快速排序分區邏輯、歸並合併邏輯、二分查找邊界條件

測試代碼

$arr = [12, 5, 4, 7, 8, 3, 4, 2, 6, 4, 9];
echo "原始: " . implode(',', $arr) . "\n";
echo "冒泡: " . implode(',', bubble_sort($arr)) . "\n";
echo "選擇: " . implode(',', select_sort($arr)) . "\n";
echo "插入: " . implode(',', insert_sort($arr)) . "\n";
echo "快速: " . implode(',', quick_sort($arr)) . "\n";
echo "歸並: " . implode(',', merge_sort($arr)) . "\n";

$sorted = [1,2,3,4,5,6,7,8,9];
echo "二分遞歸查找 5: " . bin_search_recursive($sorted, 0, 8, 5) . "\n"; // 4
echo "二分迭代查找 5: " . bin_search_iterative($sorted, 5) . "\n"; // 4