内容简介：这篇了解下快速排序。维基百科中的介绍。核心的思想是使用
导语
这篇了解下快速排序。
快速排序
快速排序（英语：Quicksort），又称 划分交换排序 （partition-exchange sort），简称 快排 ，一种 排序算法 ，最早由 东尼·霍尔 提出。在平均状况下，排序 n 个项目要 O(n log n) 次比较。在最坏状况下则需要 O(n 2 ) 次比较，但这种状况并不常见。事实上，快速排序 O(n log n) 通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。
步骤为：
- 从数列中挑出一个元素，称为"基准"（pivot），
- 重新 排序 数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为 分区（partition） 操作。
- 递归 地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
维基百科中的介绍。核心的思想是使用 递归 ，下面的动图很形象。
动图演示
实例
<?php
$arr = [33, 24, 8, 21, 2, 23, 3, 32, 16];
function quickSort($arr)
{
$count = count($arr);
if ($count < 2) {
return $arr;
}
$leftArray = $rightArray = array();
$middle = $arr[0];// 基准值
for ($i = 1; $i < $count; $i++) {
// 小于基准值，存入左边；大于基准值，存入右边
if ($arr[$i] < $middle) {
$leftArray[] = $arr[$i];
} else {
$rightArray[] = $arr[$i];
}
}
$leftArray = quickSort($leftArray);
$rightArray = quickSort($rightArray);
return array_merge($leftArray, array($middle), $rightArray);
// 倒序
// return array_merge($rightArray, array($middle), $leftArray);
}
print_r(quickSort($arr));
// Array ( [0] => 2 [1] => 3 [2] => 8 [3] => 16 [4] => 21 [5] => 23 [6] => 24 [7] => 32 [8] => 33 )
参考资料： 快速排序 、 PHP 快速排序算法 、 GIF演示排序算法 。
以上所述就是小编给大家介绍的《PHP 实现快速排序》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
