如何用PHP實現一個簡單的排序演算法（如冒泡排序）?

冒泡排序是一種簡單直觀的排序演算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。

冒泡排序 (Bubble Sort) 的 PHP 實現

PHP

<?php

/**
 * 實現冒泡排序演算法
 *
 * @param array $arr 待排序的陣列
 * @return array 排序後的陣列
 */
function bubbleSort(array $arr): array
{
    $n = 0;

    // 手動計算陣列長度，不使用 count()
    foreach ($arr as $item) {
        $n++;
    }

    // 外層迴圈控制排序的趟數
    // 每一趟都會將最大的元素「冒泡」到陣列的末尾
    for ($i = 0; $i < $n - 1; $i++) {
        // 內層迴圈進行比較和交換
        // 每次迴圈會從頭開始比較到未排序部分的末尾
        // 由於每完成一趟，最後一個元素就已經歸位，
        // 所以下一次內層迴圈可以少比較一個元素 (n - 1 - i)
        $swapped = false; // 優化：如果一趟內沒有任何交換發生，表示陣列已經有序，可以提前結束
        for ($j = 0; $j < $n - 1 - $i; $j++) {
            // 如果當前元素大於下一個元素，則交換它們的位置
            if ($arr[$j] > $arr[$j + 1]) {
                // 交換操作 (可以透過臨時變數實現，或使用 PHP 的 list/array destructuring)
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
                $swapped = true; // 發生了交換
            }
        }

        // 如果在一趟完整的迴圈中都沒有發生交換，則表示陣列已經排序完成
        if (!$swapped) {
            break;
        }
    }

    return $arr;
}

// 測試範例
$numbers1 = [64, 34, 25, 12, 22, 11, 90];
$numbers2 = [5, 1, 4, 2, 8];
$numbers3 = [1, 2, 3, 4, 5]; // 已經排序好的陣列
$numbers4 = [5, 4, 3, 2, 1]; // 逆序陣列
$numbers5 = []; // 空陣列
$numbers6 = [7]; // 單一元素陣列

echo "原始陣列: " . implode(", ", $numbers1) . " => 排序後: " . implode(", ", bubbleSort($numbers1)) . "\n";
echo "原始陣列: " . implode(", ", $numbers2) . " => 排序後: " . implode(", ", bubbleSort($numbers2)) . "\n";
echo "原始陣列: " . implode(", ", $numbers3) . " => 排序後: " . implode(", ", bubbleSort($numbers3)) . "\n";
echo "原始陣列: " . implode(", ", $numbers4) . " => 排序後: " . implode(", ", bubbleSort($numbers4)) . "\n";
echo "原始陣列: " . implode(", ", $numbers5) . " => 排序後: " . implode(", ", bubbleSort($numbers5)) . "\n";
echo "原始陣列: " . implode(", ", $numbers6) . " => 排序後: " . implode(", ", bubbleSort($numbers6)) . "\n";

?>

程式碼解釋

1. bubbleSort(array $arr): array 函數定義：

   • 接受一個陣列 $arr 作為輸入，並返回一個陣列。

2. 計算陣列長度 (不使用 count())

   • foreach ($arr as $item) { $n++; }：為了符合不使用內建函數的要求，這裡手動迭代陣列來計算其元素數量，並存儲在 $n 中。

3. 外層迴圈 for ($i = 0; $i < $n - 1; $i++)：

   • 這個迴圈控制冒泡排序的「趟數」。
   • 總共需要進行 n-1 趟排序，因為每趟至少有一個元素會被放到正確的位置（最大的元素會「冒泡」到最右邊）。

4. 內層迴圈 for ($j = 0; $j < $n - 1 - $i; $j++)：

   • 這個迴圈負責在每一趟中進行實際的元素比較和交換。
   • $n - 1 - $i：注意這裡的上限。
     • 在第一趟 ($i=0$)，我們需要比較到倒數第二個元素 ($n-1)，因為 $arr[$j+1] 存在。
     • 在第二趟 ($i=1$)，最後一個元素已經歸位，所以我們只需要比較到倒數第三個元素 ($n-2)，依此類推。這樣可以減少不必要的比較次數。

5. 比較與交換：if ($arr[$j] > $arr[$j + 1])

   • 如果當前元素 $arr[$j] 大於其後一個元素 $arr[$j + 1]，則說明它們的順序不正確。
   • 交換操作：
     • $temp = $arr[$j];：將當前元素的值暫存到一個臨時變數 $temp 中。
     • $arr[$j] = $arr[$j + 1];：將後一個元素的值賦給當前位置。
     • $arr[$j + 1] = $temp;：將暫存的值賦給後一個位置，完成交換。
     • 也可以使用 PHP 7.1+ 的陣列解構賦值來交換：[$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]]; 但為了兼容性和不依賴內建特性，我們使用傳統的臨時變數方法。

6. 優化：$swapped 旗標：

   • if (!$swapped) { break; }：這是一個常見的冒泡排序優化。如果在內層迴圈的某一趟中，沒有發生任何元素交換，這表示陣列已經是完全排序好的了，我們就可以提前結束外層迴圈，提高效率。

冒泡排序的特性

• 時間複雜度：
  • 最佳情況： O(n)（陣列已經有序，只需要一趟遍歷，$swapped 旗標會使其提前終止）。
  • 最差情況： O(n2)（陣列逆序，需要完成所有的比較和交換）。
  • 平均情況： O(n2)。
• 空間複雜度： O(1)（只需要常數額外的空間用於交換元素）。
• 穩定性： 冒泡排序是穩定的排序演算法，即相等元素的相對順序在排序後不會改變。

何時使用冒泡排序？

儘管冒泡排序是一個很直觀的演算法，但在實際開發中，由於其較差的平均和最差時間複雜度 (O(n2))，它很少用於大型數據集。在大多數情況下，我們會選擇更有效率的排序演算法，如快速排序 (Quick Sort)、合併排序 (Merge Sort) 或內建的 sort()、asort() 等 PHP 函數。

然而，學習冒泡排序對於理解排序演算法的基本原理非常有幫助，它也是面試中常見的考題之一。

希望這個實現能幫助您理解冒泡排序的運作方式！