算法原理

下列动图来自@五分钟学算法,演示了快速排序算法的原理和步骤。

自动草稿

步骤:

  • 从数组中选个基准值
  • 将数组中大于基准值的放同一边、小于基准值的放另一边,基准值位于中间位置
  • 递归的对分列两边的数组再排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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);
}

测试代码:

1
2
3
4
5
6
7
8
9
10
$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, “sn”;

测试结果:

1
2
3
before sort: 1, 7, 10, 9, 6, 3, 2, 5, 4, 8
after sort: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
use time: 0.0009009838104248s

时间复杂度

快速排序的时间复杂度在最坏情况下是O(N2),平均的时间复杂度是O(N*lgN)

这句话很好理解:假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N),需要遍历多少次呢?至少lg(N+1)次,最多N次。

1) 为什么最少是lg(N+1)次?快速排序是采用的分治法进行遍历的,我们将它看作一棵二叉树,它需要遍历的次数就是二叉树的深度,而根据完全二叉树的定义,它的深度至少是lg(N+1)。因此,快速排序的遍历次数最少是lg(N+1)次。

2) 为什么最多是N次?这个应该非常简单,还是将快速排序看作一棵二叉树,它的深度最大是N。因此,快读排序的遍历次数最多是N次。

免责申明:
1. 本站所有教程、文章分享目的仅供大家学习和交流,资源连接来自于网络,非本站发布,本站也不存储任何资源!
2. 如有无法查看或链接失效,烦请报告联系管理员处理!
3. 本站无法保证资源作或其时效性,恕不接受任何提问。
4.本站即不保存任何资源,也不对任何链接作品负责,希望大家赞助本站,费用仅维持本站的日常运营所需!
5. 百码云无法保证文章教程或资源的完善与安全,请自行检测解决。
6. 通过本站收集链接的相关资源,严禁杜绝任何形式的正式商业用途,请前往官方购买。
百码云资源站仅提供学习的平台,所有资料均来自于网络,版权归原创者所有!本站不提供任何保证,并不承担任何法律责任,如果对您的版权或者利益造成损害,请提供相应的资质证明,我们将于3个工作日内予以删除。本作品采用BY-NC-SA 4.0 《国际知识共享署名许可协议4.0》 进行许可 。
百码云 » PHP 算法 —— 快速排序

提供最优质的资源集合

关于VIP 站内帮助