排序演算法是程式設計基礎核心。雖然 PHP 內建 sort()、usort() 等高效能 C 語言實作,但理解經典演算法原理對於面試、教學、特定場景優化 (如大量資料外部排序、自訂比較邏輯) 至關重要。本文實作六大經典排序並分析時空間複雜度。
| 演算法 | 平均時間 | 最好 | 最壞 | 空間 | 穩定性 | 類型 |
|---|---|---|---|---|---|---|
| 插入排序 | O(n²) | O(n) | O(n²) | O(1) | 穩定 | 原地比較 |
| 選擇排序 | O(n²) | O(n²) | O(n²) | O(1) | 不穩定 | 原地比較 |
| 冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | 穩定 | 原地比較 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 不穩定 | 分治遞迴 |
| 合併排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 穩定 | 分治遞迴 |
| 堆積排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不穩定 | 樹結構 |
<?php
function insertionSort(array $arr): array
{
$n = count($arr);
for ($i = 1; $i < $n; $i++) {
$key = $arr[$i];
$j = $i - 1;
// 將大於 key 的元素右移
while ($j >= 0 && $arr[$j] > $key) {
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $key;
}
return $arr;
}
特點:原地排序、穩定、最佳情況 O(n) (已排序)、線上演算法 (可邊讀取邊排序)。
<?php
function selectionSort(array $arr): array
{
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
$minIdx = $i;
for ($j = $i + 1; $j < $n; $j++) {
if ($arr[$j] < $arr[$minIdx]) {
$minIdx = $j;
}
}
if ($minIdx !== $i) {
[$arr[$i], $arr[$minIdx]] = [$arr[$minIdx], $arr[$i]]; // PHP 7.1+ 解構賦值
}
}
return $arr;
}
特點:不穩定、交換次數固定 n-1 次、不適合大量資料。
<?php
function bubbleSort(array $arr): array
{
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
$swapped = false;
// 每輪將最大值「冒泡」到末尾
for ($j = 0; $j < $n - 1 - $i; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
[$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
$swapped = true;
}
}
if (!$swapped) break; // 本輪無交換,已排序完成
}
return $arr;
}
<?php
function quickSort(array $arr): array
{
$n = count($arr);
if ($n <= 1) return $arr;
$pivot = $arr[0]; // 基準值 (可優化: 三數取中、隨機)
$left = $right = [];
for ($i = 1; $i < $n; $i++) {
if ($arr[$i] <= $pivot) {
$left[] = $arr[$i];
} else {
$right[] = $arr[$i];
}
}
return array_merge(quickSort($left), [$pivot], quickSort($right));
}
// 原地快速排序 (省記憶體、較複雜)
function quickSortInPlace(array &$arr, int $low, int $high): void
{
if ($low < $high) {
$pi = partition($arr, $low, $high);
quickSortInPlace($arr, $low, $pi - 1);
quickSortInPlace($arr, $pi + 1, $high);
}
}
function partition(array &$arr, int $low, int $high): int
{
$pivot = $arr[$high];
$i = $low - 1;
for ($j = $low; $j < $high; $j++) {
if ($arr[$j] <= $pivot) {
$i++;
[$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
}
}
[$arr[$i + 1], $arr[$high]] = [$arr[$high], $arr[$i + 1]];
return $i + 1;
}
<?php
function mergeSort(array $arr): array
{
$n = count($arr);
if ($n <= 1) return $arr;
$mid = $n >> 1;
$left = mergeSort(array_slice($arr, 0, $mid));
$right = mergeSort(array_slice($arr, $mid));
return merge($left, $right);
}
function merge(array $left, array $right): array
{
$result = [];
$i = $j = 0;
while ($i < count($left) && $j < count($right)) {
if ($left[$i] <= $right[$j]) {
$result[] = $left[$i++];
} else {
$result[] = $right[$j++];
}
}
// 合併剩餘
while ($i < count($left)) $result[] = $left[$i++];
while ($j < count($right)) $result[] = $right[$j++];
return $result;
}
<?php
function heapSort(array $arr): array
{
$n = count($arr);
// 建立最大堆
for ($i = ($n >> 1) - 1; $i >= 0; $i--) {
heapify($arr, $n, $i);
}
// 逐一取出堆頂
for ($i = $n - 1; $i > 0; $i--) {
[$arr[0], $arr[$i]] = [$arr[$i], $arr[0]]; // 根與末尾交換
heapify($arr, $i, 0); // 重新調整縮小後的堆
}
return $arr;
}
function heapify(array &$arr, int $n, int $i): void
{
$largest = $i;
$left = 2 * $i + 1;
$right = 2 * $i + 2;
if ($left < $n && $arr[$left] > $arr[$largest]) $largest = $left;
if ($right < $n && $arr[$right] > $arr[$largest]) $largest = $right;
if ($largest !== $i) {
[$arr[$i], $arr[$largest]] = [$arr[$largest], $arr[$i]];
heapify($arr, $n, $largest);
}
}
<?php
$data = range(1, 100000);
shuffle($data);
$algos = [
'PHP sort()' => fn($a) => sort($a),
'快速排序' => 'quickSort',
'合併排序' => 'mergeSort',
'堆積排序' => 'heapSort',
'插入排序' => 'insertionSort', // 10萬筆會非常慢,略過
'選擇排序' => 'selectionSort', // 同略過
'冒泡排序' => 'bubbleSort', // 同略過
];
foreach ($algos as $name => $fn) {
$testData = $data;
$start = microtime(true);
if (is_string($fn)) $fn($testData); else $fn($testData);
$time = microtime(true) - $start;
echo sprintf("%-15s: %.4f 秒\n", $name, $time);
}
/* 典型輸出:
PHP sort() : 0.0123 秒 (C 實作,極快)
快速排序 : 0.1567 秒
合併排序 : 0.2345 秒
堆積排序 : 0.3124 秒
*/
| 函數 | 說明 | 保留鍵值 | 比較方式 |
|---|---|---|---|
sort() | 值排序,重建索引 | 否 | 值比較 |
rsort() | 值降序,重建索引 | 否 | 值比較 |
asort() | 值排序,保留鍵值關聯 | 是 | 值比較 |
arsort() | 值降序,保留鍵值 | 是 | 值比較 |
ksort() | 鍵值排序,保留關聯 | 是 | 鍵比較 |
krsort() | 鍵值降序 | 是 | 鍵比較 |
usort() | 自訂比較函數,重建索引 | 否 | 回呼函數 |
uasort() | 自訂比較,保留鍵值 | 是 | 回呼函數 |
uksort() | 自訂鍵比較,保留鍵值 | 是 | 回呼函數 |
natsort() | 自然排序 (字串數字順序) | 是 | 自然順序 |
<?php
$users = [
['name' => 'Tom', 'age' => 25],
['name' => 'Jerry', 'age' => 20],
['name' => 'Spike', 'age' => 30],
];
// 年齡升序
usort($users, fn($a, $b) => $a['age'] <=> $b['age']); // PHP 7 太空船運算子
// 複合排序:年齡升序,同齡則名稱降序
usort($users, function($a, $b) {
return [$a['age'], $b['name']] <=> [$b['age'], $a['name']];
});
實務開發中 **99% 情況直接使用 PHP 內建排序函數** (sort/usort 等),效能極佳且經過充分測試。手寫排序演算法主要用於:理解底層原理、面試準備、特殊資料結構 (如連結串列)、外部排序 (檔案大於記憶體)、教學示範。掌握各演算法特性 (穩定性、空間複雜度、最好/最壞情況) 有助於針對特定問題選擇最適合的策略。