php实现快速排序的代码示例

本篇文章给大家带来的内容是关于php实现快速排序的代码示例，有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。

快速排序

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序 n 个项目要 O(n log n) 次比较。在最坏状况下则需要 O(n2) 次比较，但这种状况并不常见。事实上，快速排序 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实现快速排序的代码示例的详细内容，PHP教程

郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。