PHP 算法 —— 快速排序
source link: https://shockerli.net/post/quick-sort-implement-by-php/?amp%3Butm_medium=referral
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
算法原理
下列动图来自 @五分钟学算法 ，演示了快速排序算法的原理和步骤。
步骤:
- 从数组中选个基准值
- 将数组中大于基准值的放同一边、小于基准值的放另一边，基准值位于中间位置
- 递归的对分列两边的数组再排序
代码实现
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);
}
测试代码:
$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, "s\n";
测试结果:
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次。
参考资料
Recommend
-
91
数据结构与算法—快速排序（Java实现）
-
39
夯实算法-快速排序 2020-03-01 / / 168 点击 / 阅读耗时 7 分钟...
-
6
快速选择算法详解 👆让天下没有难刷的算法！若 GitBook 访问太慢，可尝试
-
6
快速排序与冒泡排序类似，也属于交换排序，通过元素之间的比较和交换位置实现排序。不同的地方在于，冒泡排序在每一次循环只把一个元素冒泡到数组的一端，而快速排序在每一轮挑选一个枢纽元，并让其他比它大的元素移动到数组的一边，...
-
6
golang 快速排序与 PHP 快速排序 xiaojinglong123 · 2天之前 · 231 次点击 · 预计阅读时间...
-
3
1) 冒泡排序 冒泡排序在众多排序算法中算比较简单的一个, 基本思想是, 重复的进行整个数列的排序, 一次比较两个元素(两两排序),如果它们顺序不符合就交换,重复这样直到数列没有再需要交换的数为止(结束条件).就...
-
3
快速排序，又称分区交换排序，简称快排。它也是一种交换排序，它是一种在处理大量数据方面有优势的算法。当数据量巨大的时候，冒泡排序这种中规中矩，挨次遍历逐个对比的玩法，估计会让人抓毛的，于是据说在公元1960年，一位叫东尼·霍...
-
4
手撕排序算法系列之第五篇：快速排序。从本篇文章开始，我会介绍并分析常见的几种排序，大致包括 直接插入排序， 冒泡排...
-
0
PHP之快速排序的实现 发表于 2017-12-28 | 分类于 开发 | | 浏览4 次 | 字数统计: 382 | 阅读时长 ≈ 1快速排序（Quicksort）是对冒泡排序的一种改进。快速排序由C. A....
-
5
今天总结一下非常有用的快速排序(qsort)算法, 以及由此衍生的一些其他相关算法(Knuth shuffle, quick select, 3-way partition). 快速排序的算法可以用三句话描述:[Algo] 选择基准项(pivot element, 一般取...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK