快速排序是一种高效的排序算法，由英国计算机科学家C.A.R. Hoare在1960年提出。该算法基于“分而治之”(Divide and Conquer)的策略，通过选择一个基准值并重新排列数组，使得基准值位于正确的位置（通常是最中间），然后递归地对数组的两部分进行同样的操作，直到所有元素都排好序。
**算法原理**
1. **选取基准值**：从数组中随机或选择一个元素作为基准值，这里用的是数组的第一个元素 `$v`。
2. **分区**：遍历数组，将所有小于基准值的元素放入一个新数组 `$low`，大于等于基准值的元素放入另一个新数组 `$up`。这样，基准值就被放在了两个子数组的中间，形成了一个分割点。
3. **递归排序**：对 `$low` 和 `$up` 数组分别执行快速排序，直到子数组的长度为1或0，递归结束。
**代码实现**
```php
function quickSort($arr) {
$len = count($arr);
if ($len <= 1) {
return $arr;
}
$v = $arr[0];
$low = $up = array();
for ($i = 1; $i < $len; ++$i) {
if ($arr[$i] > $v) {
$up[] = $arr[$i];
} else {
$low[] = $arr[$i];
}
}
$low = quickSort($low);
$up = quickSort($up);
return array_merge($low, array($v), $up);
}
```
**测试代码**
```php
$startTime = microtime(1);
$arr = range(1, 10);
shuffle($arr);
echo "before sort: ", implode(', ', $arr), "\n";
$sortArr = quickSort($arr);
echo "after sort: ", implode(', ', $sortArr), "\n";
echo "use time: ", microtime(1) - $startTime, "s\n";
```
**时间复杂度**
快速排序的平均时间复杂度为 O(N log N)，这是因为它每次划分操作都能将问题规模减半。最坏的情况是当输入数组已经排序或几乎排序时，时间复杂度会退化到 O(N^2)。但这种情况在实际应用中很少出现，因为通常会选择随机的基准值来避免这种情况。
1. **为什么最少是 lg(N+1) 次？**
快速排序可以看作是一棵平衡的二叉搜索树，若每次划分都是均匀的，则树的高度为 log2(N+1)，即遍历次数至少为 lg(N+1)。
2. **为什么最多是 N 次？**
如果每次划分都非常不均匀，例如每次都将一个大数组分为一个元素和剩下所有元素，此时快速排序退化成冒泡排序，树的高度变为 N，遍历次数最多为 N 次。
**总结**
PHP 实现的快速排序算法简洁明了，利用递归将问题分解，通过不断地分区和排序达到排序的目的。尽管最坏情况下的时间复杂度较高，但在实际应用中，由于随机选取基准值，快速排序通常表现出良好的性能，是实践中常用的排序算法之一。
