网上有关“快速排序算法”话题很是火热，小编也是针对快速排序算法寻找了一些与之相关的一些信息进行分析，如果能碰巧解决你现在面临的问题，希望能够帮助到您。
第一趟排序后数组中的元素排列为37、35、38、36、47、53、65、73；
第二趟排序后数组中的元素排列为36、35、37、38、47、53、65、73；
第三趟排序后数组中的元素排列为35、36、37、38、47、53、65、73；
第四趟排序后数组中的元素排列为35、36、37、38、47、53、65、73；
第五趟排序后数组中的元素排列为35、36、37、38、47、53、65、73；
第六趟排序后数组中的元素排列为35、36、37、38、47、53、65、73；
第七趟排序后数组中的元素排列为35、36、37、38、47、53、65、73；
第八趟排序后数组中的元素排列为35、36、37、38、47、53、65、73。
算法原理
下列动图来自五分钟学算法，演示了快速排序算法的原理和步骤。
步骤:
从数组中选个基准值
将数组中大于基准值的放同一边、小于基准值的放另一边，基准值位于中间位置
递归的对分列两边的数组再排序
代码实现
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次。
您可能感兴趣的文章:PHP快速排序算法实例分析PHP四种排序算法实现及效率分析冒泡排序,插入排序,选择排序和快速排序PHP排序算法之快速排序(Quick
Sort)及其优化算法详解PHP递归实现快速排序的方法示例php
二维数组快速排序算法的实现代码PHP常用排序算法实例小结基本排序，冒泡排序，快速排序，插入排序PHP快速排序quicksort实例详解
关于“快速排序算法”这个话题的介绍，今天小编就给大家分享完了，如果对你有所帮助请保持对本站的关注！
本文来自作者[香萱]投稿，不代表欧拉号立场，如若转载，请注明出处：https://cn.ooplay.net/oula/36.html
评论列表（3条）
我是欧拉号的签约作者“香萱”
本文概览：网上有关“快速排序算法”话题很是火热，小编也是针对快速排序算法寻找了一些与之相关的一些信息进行分析，如果能碰巧解决你现在面临的问题，希望能够帮助到您。第一趟排序后数组中的元素排...
文章不错《快速排序算法》内容很有帮助