PHP快速排序算法实现的原理及代码详解
发布网友
发布时间：2022-04-22 23:00
共2个回答
懂视网
时间：2022-04-06 04:46
php实现快速排序的方法：首先创建一个PHP示例文件；然后创建交换函数和主函数；接着对低子表和高子表进行递归排序；最后调用QuickSort算法即可。
推荐：《PHP视频教程》
基本思想：
快速排序（Quicksort）是对冒泡排序的一种改进。他的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行快速排序，整个排序过程可以递归进行，以达到整个序列有序的目的。
基本算法步骤：
举个栗子： 
假如现在待排序记录是：
6 2 7 3 8 9
第一步、创建变量 $low 指向记录中的第一个记录，$high 指向最后一个记录，$pivot 作为枢轴赋值为待排序记录的第一个元素（不一定是第一个），这里：
$low = 0; $high = 5; $pivot = 6;
第二步、我们要把所有比 $pivot 小的数移动到 $pivot 的左面，所以我们可以开始寻找比6小的数，从 $high 开始，从右往左找，不断递减变量 $high 的值，我们找到第一个下标 3 的数据比 6 小，于是把数据 3 移到下标 0 的位置（$low 指向的位置），把下标 0 的数据 6 移到下标 3，完成第一次比较：
3 2 7 6 8 9 //这时候,$high 减小为 3 $low = 0; $high = 3; $pivot = 6;
第三步、我们开始第二次比较，这次要变成找比 $pivot 大的了，而且要从前往后找了。递加变量 $low，发现下标 2 的数据是第一个比 $pivot 大的，于是用下标 2 （$low 指向的位置）的数据 7 和 指向的下标 3 （$high 指向的位置）的数据的 6 做交换，数据状态变成下表：
3 2 6 7 8 9 //这时候,$high 减小为 3 $low = 2; $high = 3; $pivot = 6;
完成第二步和第三步我们称为完成一个循环。
第四步（也就是开启下一个循环）、模仿第二步的过程执行。
第五步、模仿第三步的过程执行。
执行完第二个循环之后，数据状态如下：
3 2 6 7 8 9 //这时候,$high 减小为 3 $low = 2; $high = 2; $pivot = 6;
到了这一步，我们发现 $low 和 $high“碰头”了：他们都指向了下标 2。于是，第一遍比较结束。得到结果如下，凡是 $pivot(=6) 左边的数都比它小，凡是 $pivot 右边的数都比它大。
然后，对 、$pivot 两边的数据 {3，2} 和 {7，8，9}，再分组分别进行上述的过程，直到不能再分组为止。
注意：第一遍快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。
算法实现：
//交换函数
function swap(array &$arr,$a,$b){
$temp = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
}
//主函数：
function QuickSort(array &$arr){
$low = 0;
$high = count($arr) - 1;
QSort($arr,$low,$high);
}主函数中，由于第一遍快速排序是对整个数组排序的，因此开始是 $low=0,$high=count($arr)-1。
然后 QSort() 函数是个递归调用过程，因此对它封装了一下：
function QSort(array &$arr,$low,$high){
//当 $low >= $high 时表示不能再进行分组，已经能够得出正确结果了
if($low < $high){
$pivot = Partition($arr,$low,$high); //将$arr[$low...$high]一分为二，算出枢轴值
QSort($arr,$low,$pivot - 1); //对低子表（$pivot左边的记录）进行递归排序
QSort($arr,$pivot + 1,$high); //对高子表（$pivot右边的记录）进行递归排序
}
}从上面的 QSort（）函数中我们看出，Partition（）函数才是整段代码的核心，因为该函数的功能是：选取当中的一个关键字，比如选择第一个关键字。然后想尽办法将它放到某个位置，使得它左边的值都比它小，右边的值都比它大，我们将这样的关键字成为枢轴（pivot）。
直接上代码：
//选取数组当中的一个关键字，使得它处于数组某个位置时，左边的值比它小，右边的值比它大，该关键字叫做枢轴
//使枢轴记录到位，并返回其所在位置
function Partition(array &$arr,$low,$high){
$pivot = $arr[$low]; //选取子数组第一个元素作为枢轴
while($low < $high){ //从数组的两端交替向中间扫描（当 $low 和 $high 碰头时结束循环）
while($low < $high && $arr[$high] >= $pivot){
$high --;
}
swap($arr,$low,$high); //终于遇到一个比$pivot小的数，将其放到数组低端
while($low < $high && $arr[$low] <= $pivot){
$low ++;
}
swap($arr,$low,$high); //终于遇到一个比$pivot大的数，将其放到数组高端
}
return $low; //返回high也行，毕竟最后low和high都是停留在pivot下标处
}组合起来的整个代码如下：
function swap(array &$arr,$a,$b){
$temp = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
}
function Partition(array &$arr,$low,$high){
$pivot = $arr[$low]; //选取子数组第一个元素作为枢轴
while($low < $high){ //从数组的两端交替向中间扫描
while($low < $high && $arr[$high] >= $pivot){
$high --;
}
swap($arr,$low,$high); //终于遇到一个比$pivot小的数，将其放到数组低端
while($low < $high && $arr[$low] <= $pivot){
$low ++;
}
swap($arr,$low,$high); //终于遇到一个比$pivot大的数，将其放到数组高端
}
return $low; //返回high也行，毕竟最后low和high都是停留在pivot下标处
}
function QSort(array &$arr,$low,$high){
if($low < $high){
$pivot = Partition($arr,$low,$high); //将$arr[$low...$high]一分为二，算出枢轴值
QSort($arr,$low,$pivot - 1); //对低子表进行递归排序
QSort($arr,$pivot + 1,$high); //对高子表进行递归排序
}
}
function QuickSort(array &$arr){
$low = 0;
$high = count($arr) - 1;
QSort($arr,$low,$high);
}我们调用算法：
$arr = array(9,1,5,8,3,7,4,6,2); QuickSort($arr); var_dump($arr);
复杂度分析：
在最优的情况下，也就是选择数轴处于整个数组的中间值的话，则每一次就会不断将数组平分为两半。因此最优情况下的时间复杂度是 O(nlogn) （跟堆排序、归并排序一样）。
最坏的情况下，待排序的序列是正序或逆序的，那么在选择枢轴的时候只能选到边缘数据，每次划分得到的比上一次划分少一个记录，另一个划分为空，这样的情况的最终时间复杂度为 O(n^2).
综合最优与最差情况，平均的时间复杂度是 O(nlogn).
快速排序是一种不稳定排序方法。
由于快速排序是个比较高级的排序，而且被列为20世纪十大算法之一。。。。如此牛掰的算法，我们还有什么理由不去学他呢！
尽管这个算法已经很牛掰了，但是上面的算法程序依然有改进的地方。
热心网友
时间：2022-04-06 01:54
下列动图来自五分钟学算法，演示了快速排序算法的原理和步骤。
步骤:
从数组中选个基准值
将数组中大于基准值的放同一边、小于基准值的放另一边，基准值位于中间位置
递归的对分列两边的数组再排序
代码实现
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实例详解
