快速排序
<ul>
<li>每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。</li>
<li>这样在每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进行交换，交换的距离就大得多了。
因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。</li>
<li>因此快速排序的最差时间复杂度和冒泡排序是一样的，都是 O(N2)，它的平均时间复杂度为 O (NlogN)。
其实快速排序是基于一种叫做“二分”的思想。不稳定排序</li>
</ul>
<h2>实现</h2>
<pre><code class="language-php">function quick1(array $arr)
{
// 判断是否需要运行，因下面已拿出一个中间值
if (empty($arr) || count($arr) == 1) {
return $arr;
}
$middle = $arr[0]; // 中间值
$left = []; // 接收小于中间值
$right = [];// 接收大于中间值
// 循环比较
for ($index = 1; $index < count($arr); $index++) {
$value = $arr[$index];
if ($middle < $value) {
$right[] = $value; // 大于中间值
} else {
$left[] = $value; // 小于中间值
}
}
// 递归排序划分好的2边
$left = quick1($left);
$right = quick1($right);
// 合并排序后的数据，别忘了合并中间值
return array_merge($left, [$middle], $right);
}</code></pre>
<h2>测试</h2>
<pre><code class="language-php">$arr1 = [23, 15, 43, 25, 54, 2, 6, 82, 11, 5, 21, 32, 65];
$quick1 = quick1($arr1);
var_export($quick1);</code></pre>
<h2>结果</h2>
<pre><code class="language-php">array (
0 => 2,
1 => 5,
2 => 6,
3 => 11,
4 => 15,
5 => 21,
6 => 23,
7 => 25,
8 => 32,
9 => 43,
10 => 54,
11 => 65,
12 => 82,
)</code></pre>
<h2>实现</h2>
<pre><code class="language-php">function quick2(&$array, $startIndex, $count)
{
if ($startIndex > $count) {
return;
}
$key = $array[$startIndex]; //基数值
$left = $startIndex; //左边哨兵
$right = $count; //右边哨兵
while ($startIndex != $count) {
//往左边找第一个小于$key的值，直到找到
while ($array[$count] >= $key && $startIndex < $count) {
$count--;
}
//往右边找第一个大于$key的值，直到找到
while ($array[$startIndex] <= $key && $startIndex < $count) {
$startIndex++;
}
//两个都找到，交换
if ($startIndex < $count) {
$temp = $array[$startIndex];
$array[$startIndex] = $array[$count];
$array[$count] = $temp;
}
}
//执行下一趟快速排序
$array[$left] = $array[$startIndex];
$array[$startIndex] = $key;
quick2($array, $left, $startIndex - 1);
quick2($array, $startIndex + 1, $right);
}</code></pre>
<h2>测试</h2>
<pre><code class="language-php">$arr2 = [23, 15, 43, 25, 54, 2, 6, 82, 11, 5, 21, 32, 65];
quick2($arr2, 0, count($arr2) - 1);
var_export($arr2);</code></pre>
<h2>结果</h2>
<pre><code class="language-php">array (
0 => 2,
1 => 5,
2 => 6,
3 => 11,
4 => 15,
5 => 21,
6 => 23,
7 => 25,
8 => 32,
9 => 43,
10 => 54,
11 => 65,
12 => 82,
)</code></pre>