搜索
首页后端开发php教程PHP快速排序算法使用步骤详解

这次给大家带来PHP快速排序算法使用步骤详解,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);

运行结果:

array(9) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(4)
 [4]=>
 int(5)
 [5]=>
 int(6)
 [6]=>
 int(7)
 [7]=>
 int(8)
 [8]=>
 int(9)
}

复杂度分析:

在最优的情况下,也就是选择数轴处于整个数组的中间值的话,则每一次就会不断将数组平分为两半。因此最优情况下的时间复杂度是 O(nlogn) (跟堆排序、归并排序一样)。

最坏的情况下,待排序的序列是正序或逆序的,那么在选择枢轴的时候只能选到边缘数据,每次划分得到的比上一次划分少一个记录,另一个划分为空,这样的情况的最终时间复杂度为 O(n^2).

综合最优与最差情况,平均的时间复杂度是 O(nlogn).

快速排序是一种不稳定排序方法。

由于快速排序是个比较高级的排序,而且被列为20世纪十大算法之一。。。。如此牛掰的算法,我们还有什么理由不去学他呢!

尽管这个算法已经很牛掰了,但是上面的算法程序依然有改进的地方,下面具体讨论一下

快速排序算法优化

优化一:优化选取枢轴:

在前面的复杂度分析的过程中,我们看到最坏的情况无非就是当我们选中的枢轴是整个序列的边缘值。比如这么一个序列:

9   1   5   8   3   7   4   6   2

按照习惯我们选择数组的第一个元素作为枢轴,则 $pivot = 9,在一次循环下来后划分为{1,5,8,3,7,4,6,2} 和{ }(空序列),也就是每一次划分只得到少一个记录的子序列,而另一个子序列为空。最终时间复杂度为 O(n^2)。最优的情况是当我们选中的枢轴是整个序列的中间值。但是我们不能每次都去遍历数组拿到最优值吧?那么就有了一下解决方法:

1、随机选取:随机选取 $low 到 $high 之间的数值,但是这样的做法有些撞大运的感觉了,万一没撞成功呢,那上面的问题还是没有解决。

2、三数取中法:取三个关键字先进行排序,取出中间数作为枢轴。这三个数一般取最左端、最右端和中间三个数,也可以随机取三个数。这样的取法得到的枢轴为中间数的可能性就大大提高了。由于整个序列是无序的,随机选择三个数和从左中右端取出三个数其实就是同一回事。而且随机数生成器本身还会带来时间的开销,因此随机生成不予考虑。

出于这个想法,我们修改 Partition() 函数:

function Partition(array &$arr,$low,$high){
  $mid = floor($low + ($high - $low) / 2);  //计算数组中间的元素的下标
  if($arr[$low] > $arr[$high]){
    swap($arr,$low,$high);
  }
  if($arr[$mid] > $arr[$high]){
    swap($arr,$mid,$high);
  }
  if($arr[$low] < $arr[$mid]){
    swap($arr,$low,$mid);
  }
  //经过上面三步之后,$arr[$low]已经成为整个序列左中右端三个关键字的中间值
  $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下标处
}

三数取中法对于小数组有很大可能能沟得出比较理想的 $pivot,但是对于大数组就未必了,因此还有个办法是九数取中法。。。。。。

优化二:优化不必要的交换:

现在假如有个待排序的序列如下:

5   1   9   3   7   4   8   6   2

根据三数取中法我们取 5 7 2 中的 5 作为枢轴。

当你按照快速排序算法走一个循环,你会发现 5 的下标变换顺序是这样的:0 -> 8 -> 2 -> 5 -> 4,但是它的最终目标就是 4 的位置,当中的交换其实是不需要的。

根据这个思想,我们改进我们的 Partition() 函数:

function Partition(array &$arr,$low,$high){
  $mid = floor($low + ($high - $low) / 2);  //计算数组中间的元素的下标
  if($arr[$low] > $arr[$high]){
    swap($arr,$low,$high);
  }
  if($arr[$mid] > $arr[$high]){
    swap($arr,$mid,$high);
  }
  if($arr[$low] < $arr[$mid]){
    swap($arr,$low,$mid);
  }
  //经过上面三步之后,$arr[$low]已经成为整个序列左中右端三个关键字的中间值
  $pivot = $arr[$low];
  $temp = $pivot;
  while($low < $high){  //从数组的两端交替向中间扫描(当 $low 和 $high 碰头时结束循环)
    while($low < $high && $arr[$high] >= $pivot){
      $high --;
    }
    //swap($arr,$low,$high); //终于遇到一个比$pivot小的数,将其放到数组低端
    $arr[$low] = $arr[$high];  //使用替换而不是交换的方式进行操作
    while($low < $high && $arr[$low] <= $pivot){
      $low ++;
    }
    //swap($arr,$low,$high); //终于遇到一个比$pivot大的数,将其放到数组高端
    $arr[$high] = $arr[$low];
  }
  $arr[$low] = $temp;  //将枢轴数值替换回 $arr[$low];
  return $low;  //返回high也行,毕竟最后low和high都是停留在pivot下标处
}

在上面的改进中,我们使用替换而不是交进行操作,由于在这当中少了多次的数据交换,因此在性能上也是有所提高的。

优化三:优化小数组的排序方案:

对于一个数学科学家、博士生导师,他可以攻克世界性的难题,可以培育最优秀的数学博士,当让他去教小学生“1 + 1 = 2”的算术课程,那还真未必比常年在小学里耕耘的数学老师教的好。换句话说,大材小用有时会变得反而不好用。

也就是说,快速排序对于比较大数组来说是一个很好的排序方案,但是假如数组非常小,那么快速排序算法反而不如直接插入排序来得更好(直接插入排序是简单排序中性能最好的)。其原因在于快速排序用到了递归操作,在大量数据排序的时候,这点性能影响相对于它的整体算法优势而言是可以忽略的,但如果数组只有几个记录需要排序时,这就成了大炮打蚊子的大问题。

因此我们需要修改一下我们的 QSort() 函数:

//规定数组长度阀值
#define MAX_LENGTH_INSERT_SORT 7
function QSort(array &$arr,$low,$high){
  //当 $low >= $high 时表示不能再进行分组,已经能够得出正确结果了
  if(($high - $low) > MAX_LENGTH_INSERT_SORT){
    $pivot = Partition($arr,$low,$high); //将$arr[$low...$high]一分为二,算出枢轴值
    QSort($arr,$low,$pivot - 1); //对低子表($pivot左边的记录)进行递归排序
    QSort($arr,$pivot + 1,$high); //对高子表($pivot右边的记录)进行递归排序
  }else{
    //直接插入排序
    InsertSort($arr);
  }
}

PS:上面的直接插入排序算法大家可以参考:《PHP排序算法之直接插入排序(Straight Insertion Sort)》

在这里我们增加一个判断,当 $high - $low 不大于一个常数时(有资料认为 7 比较合适,也有认为 50 比较合适,实际情况可以是适当调整),就用直接插入排序,这样就能保证最大化的利用这两种排序的优势来完成排序工作。

优化四:优化递归操作:

大家知道,递归对性能时有一定影响的,QSort()函数在其尾部有两次递归的操作,如果待排序的序列划分极端不平衡(就是我们在选择枢轴的时候不是中间值),那么递归的深度将趋近于 n,而不是平衡时的 log₂n,这就不仅仅是速度快慢的问题了。

我们也知道,递归是通过栈来实现的,栈的大小是很有限的,每次递归调用都会耗费一定的栈空间,函数的参数越多,每次递归耗费的空间也越多,因此如果能减少队规,将会大大提高性能。

听说,递归都可以改造成循环实现。我们在这里就是使用循环去优化递归。(关于递归与循环大家可以参考知乎里面的讨论 《所有递归都可以改写成循环吗?》)

我们对QSort() 函数尾部递归进行优化:

//规定数组长度阀值
#define MAX_LENGTH_INSERT_SORT 7
function QSort(array &$arr,$low,$high){
  //当 $low >= $high 时表示不能再进行分组,已经能够得出正确结果了
  if(($high - $low) > MAX_LENGTH_INSERT_SORT){
    while($low < $high){
      $pivot = Partition($arr,$low,$high); //将$arr[$low...$high]一分为二,算出枢轴值
      QSort($arr,$low,$pivot - 1); //对低子表($pivot左边的记录)进行递归排序
      $low = $pivot + 1;
    }
  }else{
    //直接插入排序
    InsertSort($arr);
  }
}

在上面,我们使用循环替换递归,减少了之前一般的递归量。结果是一样的,但是采用循环而不是递归的方法可以缩减堆栈的深度,从而提高了整体性能。

相信看了本文案例你已经掌握了方法,更多精彩请关注php中文网其它相关文章!

推荐阅读:

PHP操作Redis步骤详解

PHP单例模式使用案例详解

php+receivemail做出收发邮件功能

以上是PHP快速排序算法使用步骤详解的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
php怎么把负数转为正整数php怎么把负数转为正整数Apr 19, 2022 pm 08:59 PM

php把负数转为正整数的方法:1、使用abs()函数将负数转为正数,使用intval()函数对正数取整,转为正整数,语法“intval(abs($number))”;2、利用“~”位运算符将负数取反加一,语法“~$number + 1”。

php怎么实现几秒后执行一个函数php怎么实现几秒后执行一个函数Apr 24, 2022 pm 01:12 PM

实现方法:1、使用“sleep(延迟秒数)”语句,可延迟执行函数若干秒;2、使用“time_nanosleep(延迟秒数,延迟纳秒数)”语句,可延迟执行函数若干秒和纳秒;3、使用“time_sleep_until(time()+7)”语句。

php怎么除以100保留两位小数php怎么除以100保留两位小数Apr 22, 2022 pm 06:23 PM

php除以100保留两位小数的方法:1、利用“/”运算符进行除法运算,语法“数值 / 100”;2、使用“number_format(除法结果, 2)”或“sprintf("%.2f",除法结果)”语句进行四舍五入的处理值,并保留两位小数。

php怎么根据年月日判断是一年的第几天php怎么根据年月日判断是一年的第几天Apr 22, 2022 pm 05:02 PM

判断方法:1、使用“strtotime("年-月-日")”语句将给定的年月日转换为时间戳格式;2、用“date("z",时间戳)+1”语句计算指定时间戳是一年的第几天。date()返回的天数是从0开始计算的,因此真实天数需要在此基础上加1。

php字符串有没有下标php字符串有没有下标Apr 24, 2022 am 11:49 AM

php字符串有下标。在PHP中,下标不仅可以应用于数组和对象,还可应用于字符串,利用字符串的下标和中括号“[]”可以访问指定索引位置的字符,并对该字符进行读写,语法“字符串名[下标值]”;字符串的下标值(索引值)只能是整数类型,起始值为0。

php怎么判断有没有小数点php怎么判断有没有小数点Apr 20, 2022 pm 08:12 PM

php判断有没有小数点的方法:1、使用“strpos(数字字符串,'.')”语法,如果返回小数点在字符串中第一次出现的位置,则有小数点;2、使用“strrpos(数字字符串,'.')”语句,如果返回小数点在字符串中最后一次出现的位置,则有。

php怎么替换nbsp空格符php怎么替换nbsp空格符Apr 24, 2022 pm 02:55 PM

方法:1、用“str_replace("&nbsp;","其他字符",$str)”语句,可将nbsp符替换为其他字符;2、用“preg_replace("/(\s|\&nbsp\;||\xc2\xa0)/","其他字符",$str)”语句。

php怎么读取字符串后几个字符php怎么读取字符串后几个字符Apr 22, 2022 pm 08:31 PM

在php中,可以使用substr()函数来读取字符串后几个字符,只需要将该函数的第二个参数设置为负值,第三个参数省略即可;语法为“substr(字符串,-n)”,表示读取从字符串结尾处向前数第n个字符开始,直到字符串结尾的全部字符。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前By尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
1 个月前By尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

mPDF

mPDF

mPDF是一个PHP库,可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件,并处理不同的语言。与原始脚本如HTML2FPDF相比,它的速度较慢,并且在使用Unicode字体时生成的文件较大,但支持CSS样式等,并进行了大量增强。支持几乎所有语言,包括RTL(阿拉伯语和希伯来语)和CJK(中日韩)。支持嵌套的块级元素(如P、DIV),

安全考试浏览器

安全考试浏览器

Safe Exam Browser是一个安全的浏览器环境,用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问,并防止学生使用未经授权的资源。

MinGW - 适用于 Windows 的极简 GNU

MinGW - 适用于 Windows 的极简 GNU

这个项目正在迁移到osdn.net/projects/mingw的过程中,你可以继续在那里关注我们。MinGW:GNU编译器集合(GCC)的本地Windows移植版本,可自由分发的导入库和用于构建本地Windows应用程序的头文件;包括对MSVC运行时的扩展,以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版