php 快速排序

封面图 • 2025-10-11 • PHP

在 PHP 中实现**快速排序（Quick Sort）**是一种常见的排序算法，它使用分治法（Divide and Conquer）策略来对数组进行排序。下面是一个简单的快速排序实现示例：

---

### ✅ 快速排序（Quick Sort）PHP 实现

```php
<?php

function quickSort($arr) {
    // 基本情况：如果数组长度小于等于1，直接返回
    if (count($arr) <= 1) {
        return $arr;
    }

// 选择基准值（可以是任意元素，这里选第一个）
    $pivot = $arr[0];

// 初始化左右子数组
    $left = [];   // 小于基准的元素
    $right = [];  // 大于或等于基准的元素

// 遍历数组，将元素分配到左右子数组中
    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }

// 递归地对左右子数组进行排序，并合并结果
    return array_merge(quickSort($left), [$pivot], quickSort($right));
}

// 示例用法
$array = [5, 3, 8, 4, 2, 7, 1, 10];
$sortedArray = quickSort($array);

echo "排序后的数组：\n";
print_r($sortedArray);

?>
```

---

### 🔍 算法说明：

- **基准值（pivot）**：可以选择第一个元素、最后一个元素、中间元素，或者随机选择。
- **分治**：将数组分为两部分，一部分比基准小，另一部分比基准大或相等。
- **递归**：对左右子数组递归调用 `quickSort`。
- **合并**：将排好序的左子数组、基准、排好序的右子数组合并。

---

### 🚀 时间复杂度：

- **平均情况**：O(n log n)
- **最坏情况**（如已排序数组）：O(n²)
- **空间复杂度**：O(n)（因为每次递归都创建新数组）

---

如果你希望优化性能（比如使用原地排序），可以考虑使用**Lomuto**或**Hoare**分区方法，但上面的实现更适合初学者理解。

需要我提供一个**原地排序版本**的快速排序吗？