内容简介：这篇了解下快速排序。维基百科中的介绍。核心的思想是使用
导语
这篇了解下快速排序。
快速排序
快速排序（英语：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 实现快速排序》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
The Filter Bubble
Eli Pariser / Penguin Press / 2011-5-12 / GBP 16.45
In December 2009, Google began customizing its search results for each user. Instead of giving you the most broadly popular result, Google now tries to predict what you are most likely to click on. Ac......一起来看看 《The Filter Bubble》 这本书的介绍吧!
