专栏首页决胜机器学习PHP数据结构(二十二) ——快速排序

PHP数据结构(二十二) ——快速排序

PHP数据结构(二十二)——快速排序

(原创内容,转载请注明来源,谢谢)

一、概述

前面的插入排序,都是以移动的方式进行排序。快速排序,则是以交换的方式进行排序。

二、冒泡排序

提到交换的方式进行排序,首先可以提到冒泡排序。

1、算法

冒泡排序是逐个进行比较再进行交换的排序方式,假设是以从小到大的顺序排列。

1)先用第一个数和第二个数比较,如果第一个数比较大,则和第二个数进行互换,否则两个数保持不变。

2)再用第二个数与第三个数比较,直至第n-1个数与第n个数进行比较。这称为一轮的冒泡排序。这一轮排序后,可以保证最后一个数一定是最大的。

3)再进行步骤1、2,区别在于第二轮比较到n-2和n-1的大小即可,此时保证n-1是第二大的数。此时称为完成第二轮冒泡排序。

4)以此类推,直至完成整个数组的比较,即完成冒泡排序。

2、实现源码

         //冒泡排序
         publicfunction bubbleSort(array $arr = array()){
                   $arr= $this->_checkNeedSort($arr);
                   if(!$arr){
                            return$arr;
                   }
                   //i从0开始,表示冒泡的轮数一共需要count($arr)轮
                   for($i=0;$i<count($arr);$i++){
                            //j从0开始,第一轮从0-count($arr)-1-0(后面一个0表示i=0),第二轮从0-count($arr)-1-1(后面一个1表示i=1)
                            for($j=0;$j<count($arr)-$i-1;$j++){
                                     //每次j和j+1的位置进行比较
                                     if($arr[$j]> $arr[$j+1]){
                                               $tmp= $arr[$j+1];
                                               $arr[$j+1]= $arr[$j];
                                               $arr[$j]= $tmp;
                                     }
                            }
                   }
                   return$arr;
         }

3、评价

冒泡排序效率较低,时间复杂度是O(n2),需要大量的进行数组遍历与交互。而且,无论是否数组已经排序成功,都需要不断的进行遍历。

三、快速排序

快速排序是在冒泡排序的基础上进行改进的算法。其核心思想是取数组的一个元素设定为基准值(称为枢轴或支点),其他数与这个基准值进行比较。比较结束后,将数组分为两部分,一部分为大于这个基准值的数的序列,另一部分为小于的序列,再把拆分后的序列分别再取新的枢轴进行比较。

1、算法

1)判断输入的数组,如果长度小于等于1,则直接返回,该条件作为快速排序算法结束的必须条件,否则会进入死循环。

2)挑选一个数作为基准,遍历整个数组,比它小的放在一个临时数组,比它大的放在另一个临时数组,和它一样的任意放在前面两个数组中的一个。

3)将2的两个数字分别递归调用快速排序算法,如果出现1的情况则停止递归。

4)将生成的数组合并成最终的数组。

5)tips:为了避免过多的递归,当数组长度小于某个值,比如5,可以调用其它的排序方法如插入排序,即快速排序也可以结合其他排序算法。

6)tips2:基准值建议挑选数组第一个数、最后一个数和中间数,这三个数字中,大小排在中间的那个数字。

2、实现源码

         //快速排序
         publicfunction quickSort(array $arr = array()){
                   $arr= $this->_checkNeedSort($arr);
                   if(!$arr){
                            return$arr;
                   }
                   //长度只有1直接返回
                   if(1== count($arr)){
                            return$arr;
                   }
                   //长度只有2计算后直接返回,避免过度调用
                   if(2== count($arr)){
                            return$arr[1] < $arr[0] ? array($arr[1], $arr[0]) : $arr;
                   }
                   //获取最低、中间、最大的下标
                   $low= 0;
                   $high= count($arr) - 1;
                   $mid= floor(($high + $low)/2);
                   //调用内部方法,获取三个下标对应结果的中间值,以此为基准,可以增加快速排序的效率
                   $compareVal= $this->_getKeyValue($arr[$low], $arr[$mid], $arr[$high]);
                   //两个数字分别存放比基准值小和比基准值大的数
                   //和基准值一样的数,本程序放在和比基准值大的一起
                   $leftSmallArr= array();
                   $rightBigArr= array();
                   for($i=0;$i<count($arr);$i++){
                            if($arr[$i]< $compareVal){
                                     array_push($leftSmallArr,$arr[$i]);
                            }else{
                                     array_push($rightBigArr,$arr[$i]);
                            }
                   }
                   //将生成的两个数组分别递归调用快速排序,再次进行排序
                   $leftArr= $this->quickSort($leftSmallArr);
                   $rightArr= $this->quickSort($rightBigArr);
                   //将结果数组合并
                   returnarray_merge($leftArr, $rightArr);
         }
         //快速排序使用,根据下标获取键值,取三个下标对应的值中的中间值
         privatefunction _getKeyValue($low, $middle, $high){
                   //如果middle为中间值
                   if(($middle>= $low && $middle <= $high) || ($middle <= $low &&$middle >= $high)){
                            return$middle;
                   }
                   //如果low为中间值
                   if(($low>= $middle && $low <= $high) || ($low <= $middle &&$low >= $high)){
                            return$low;
                   }
                   //如果前两个都不是,则high是中间值,不用比较
                   return$high;
         }

3、评价

快速排序时间复杂度的平均值是O(nlogn),且在所有平均的时间复杂度一样的排序方式中,效率最高。因此,该算法使用也最广泛。

但是,当基准值选的不好时,最坏情况快速排序的时间复杂度是O(n2),等同于冒泡排序。因此,基准值很重要。经过大量分析,建议选择数组中第一个数、最后一个数、中间的数,三个数的中间值作为基准值。

另外,为了减少递归的次数,当数组长度很小时,也可以用其他的排序方式进行排序。即快速排序可以结合其他排序一起进行。

——written by linhxx 2017.07.18

相关阅读:

PHP数据结构(二十一) ——希尔排序

PHP数据结构(二十) ——其他插入排序

PHP数据结构(十九) ——B+树

PHP数据结构(十八) ——直接插入排序

PHP数据结构(十七) ——内部排序综述

PHP数据结构(十六) ——B树

PHP数据结构(十五) ——哈希表​

PHP数据结构(十四) ——键树(双链树)

PHP数据结构(十三) ——动态查找表(二叉排序树)

PHP数据结构(十二) ——静态查找表​

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(1)

PHP数据结构(十) ——有向无环图与拓扑算法

PHP数据结构(九) ——图的定义、存储与两种方式遍历

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践2)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践1)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(理论)

PHP数据结构(七) ——串与实现KMP算法

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(四) ——队列

PHP数据结构(三)——运用栈实现括号匹配

PHP数据结构(二)——链式结构线性表

PHP数据结构(一)——顺序结构线性表

本文分享自微信公众号 - 决胜机器学习(phpthinker),作者:linhxx

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-07-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PHP数据结构(二十五) ——并归排序

    PHP数据结构(二十五)——并归排序 (原创内容,转载请注明来源,谢谢) 一、概述 并归排序是将两个或两个以上的有序表组合成一个新的有序表。采用并归的思想进...

    用户1327360
  • PHP数据结构(二十三) ——快速排序

    PHP数据结构(二十三)——选择排序 (原创内容,转载请注明来源,谢谢) 一、概述 选择排序的基本思想,是每一趟在n-i+1(i=1,2…n-1)个记录中选...

    用户1327360
  • PHP数据结构(十八) ——直接插入排序

    PHP数据结构(十八)——直接插入排序 (原创内容,转载请注明来源,谢谢) 一、概述 插入排序分为直接插入排序、其他插入排序、希尔排序。其他插入排序又分为折半...

    用户1327360
  • PHP数据结构(二十五) ——并归排序

    PHP数据结构(二十五)——并归排序 (原创内容,转载请注明来源,谢谢) 一、概述 并归排序是将两个或两个以上的有序表组合成一个新的有序表。采用并归的思想进...

    用户1327360
  • 程序员那些必须掌握的排序算法(上)

    现在的IT行业并不像以前那么好混了,从业人员过多,导致初级程序员过剩,这也间接导致了公司的招聘门槛越来越高,要求程序员掌握的知识也越来越多。 算法也是一个争论...

    wangweijun
  • PHP中的预定义常量

    3、__CLASS__: 类的名称(PHP 4.3.0 新加)。自 PHP 5 起本常量返回该类被定义时的名字(区分大小写)。在 PHP 4 中该值总是...

    用户7657330
  • PHP基本语法

    php超文本预处理器的字母缩写,是一种被广泛应用的开发源代码的多用途脚本语言,它可嵌入到HTML中,尤其适合web开发。

    达达前端
  • PHP 霸主地位被动摇,JIT 是穷途末路后的绝地反击?

    关键时刻,第一时间送达! 摘要:PHP 是 Web 开发最常用的语言,自创建以来,PHP 语言经历了许多激烈的改进,其中性能是开发人员在评估新版本时考虑的主要标...

    企鹅号小编
  • 【问底】徐汉彬:PHP7和HHVM的性能之争

    【导读】徐汉彬曾在阿里巴巴和腾讯从事4年多的技术研发工作,负责过日请求量过亿的Web系统升级与重构,目前在小满科技创业,从事SaaS服务技术建设。最近,PHP7...

    CSDN技术头条
  • PHP 7终于发布:开发者会选择PHP 7吗?

    大家可以通过阅读本文,学习关于PHP7.0的五个方面的内容:PHP7.0简介、主要新特性、过去几周关于程序员是否采用php7.0的意愿调查结果、以上调查结果的分...

    CSDN技术头条

作者介绍

精选专题

活动推荐

扫码关注云+社区

领取腾讯云代金券