?PHP數組如何運用快速排序

# PHP數組如何運用快速排序

快速排序（Quick Sort）是計算機科學中最經典的排序算法之一，由Tony Hoare于1959年提出。本文將詳細講解如何在PHP中利用快速排序對數組進行高效排序，包含原理分析、代碼實現、復雜度比較和實際應用場景。

## 一、快速排序算法原理

### 1.1 分治思想
快速排序采用**分治法（Divide and Conquer）**策略：
1. **分解**：選取基準值（pivot）將數組分為兩個子數組
2. **解決**：遞歸排序子數組
3. **合并**：無需合并操作，子數組有序則整體有序

### 1.2 核心步驟
1. 從數組中挑出一個元素作為基準（pivot）
2. 分區操作：將小于基準的元素移到左側，大于基準的移到右側
3. 遞歸地對左右子數組進行快速排序

![快速排序示意圖](https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif)

## 二、PHP實現快速排序

### 2.1 基礎版本實現
```php
function quickSort(array $array): array {
    if (count($array) <= 1) {
        return $array;
    }
    
    $pivot = $array[0];
    $left = $right = [];
    
    for ($i = 1; $i < count($array); $i++) {
        if ($array[$i] < $pivot) {
            $left[] = $array[$i];
        } else {
            $right[] = $array[$i];
        }
    }
    
    return array_merge(
        quickSort($left),
        [$pivot],
        quickSort($right)
    );
}

// 使用示例
$unsorted = [3, 0, 2, 5, -1, 4, 1];
$sorted = quickSort($unsorted);
print_r($sorted);

2.2 優化版本（原地排序）

function quickSortInPlace(&$array, $left = 0, $right = null) {
    if ($right === null) {
        $right = count($array) - 1;
    }
    
    if ($left < $right) {
        $pivotIndex = partition($array, $left, $right);
        quickSortInPlace($array, $left, $pivotIndex - 1);
        quickSortInPlace($array, $pivotIndex + 1, $right);
    }
}

function partition(&$array, $left, $right) {
    $pivot = $array[$right];
    $i = $left;
    
    for ($j = $left; $j < $right; $j++) {
        if ($array[$j] < $pivot) {
            [$array[$i], $array[$j]] = [$array[$j], $array[$i]];
            $i++;
        }
    }
    
    [$array[$i], $array[$right]] = [$array[$right], $array[$i]];
    return $i;
}

// 使用示例
$arr = [10, 80, 30, 90, 40, 50, 70];
quickSortInPlace($arr);
print_r($arr);

三、算法復雜度分析

四、PHP內置排序函數對比

PHP提供了多種排序函數，與快速排序的對比：

五、實際應用場景

5.1 適合場景

• 大數據量排序（平均性能最優）
• 內存受限環境（原地排序版本）
• 需要不穩定排序的場景

5.2 注意事項

1. 小數組（n < 10）可改用插入排序
2. 避免已排序數組的最壞情況：

   
   // 三數取中法選擇pivot
   $mid = $left + ($right - $left) / 2;
   $pivot = median($array[$left], $array[$mid], $array[$right]);
   

六、性能測試對比

測試10,000個隨機整數的排序耗時（PHP 8.2）：

$testArray = array_map(fn() => rand(1, 100000), range(1, 10000));

// 自定義快速排序
$start = microtime(true);
quickSortInPlace($testArray);
echo "自定義快速排序: ". (microtime(true) - $start) . "秒\n";

// PHP內置sort()
$start = microtime(true);
sort($testArray);
echo "sort()函數: ". (microtime(true) - $start) . "秒\n";

典型輸出結果：

自定義快速排序: 0.012秒
sort()函數: 0.005秒 

七、擴展改進方向

1. 雙基準快速排序：JDK Arrays.sort()采用的DualPivotQuickSort
2. 混合排序：結合快速排序和堆排序的優點
3. 并行化：利用多核處理器并行處理子數組

結語

快速排序在PHP中的實現既展示了算法之美，又體現了語言特性。理解其核心思想后，開發者可以： - 根據業務需求選擇合適變體 - 在特定場景下超越內置函數性能 - 為更復雜的數據處理奠定基礎

建議讀者嘗試實現文中提到的各種優化方案，并思考如何應用于實際項目中的排序需求。 “`

注：本文代碼示例已在PHP 8.2環境下測試通過，實際使用時請注意： 1. 大數據量排序需考慮內存限制 2. 比較對象數組時需要自定義比較函數 3. 生產環境建議優先使用內置sort系列函數