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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏玄魂工作室

面试题解:输入一个数A,找到大于A的一个最小数B,且B中不存在连续相当的两个数字

昨天发的算法有一处情况没考虑到,比如加一后有进位,导致又出现重复数字的情况,修正后今天重新发一次。

591
来自专栏恰同学骚年

剑指Offer面试题:14.链表的倒数第k个节点

PS:这是一道出境率极高的题目,记得去年参加校园招聘时我看到了3次,但是每次写的都不完善。

724
来自专栏木头编程 - moTzxx

PHP常见排序算法整理学习

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u011415782/article/de...

763
来自专栏大闲人柴毛毛

贪心算法(三)——最佳合并模式

问题描述 给定n个有序文件,每个文件的记录数分别为w1~wn,请给出一种两两合并的方案,使得总合并次数最少。 注意: 1. 外排序算法是将多个有序文件合...

36110
来自专栏目标检测和深度学习

常用排序算法总结(1)

942
来自专栏IT可乐

Java数据结构和算法(十三)——哈希表

  Hash表也称散列表,也有直接译作哈希表,Hash表是一种根据关键字值(key - value)而直接进行访问的数据结构。它基于数组,通过把关键字映射到数组...

2578
来自专栏郭耀华‘s Blog

十大经典排序算法最强总结(含JAVA代码实现)

最近几天在研究排序算法,看了很多博客,发现网上有的文章中对排序算法解释的并不是很透彻,而且有很多代码都是错误的,例如有的文章中在“桶排序”算法中对每个桶进行排...

4277
来自专栏我就是马云飞

【数据结构】七大排序算法

排序的相关概念 排序的分类 根据在排序过程中带排序的记录是否全部被放置在内存中,排序分为: 内排序 外排序 1.内排序 内排序是在排序整个过程中,带排序的所有...

18710
来自专栏老马说编程

(45) 神奇的堆 / 计算机程序的思维逻辑

前面几节介绍了Java中的基本容器类,每个容器类背后都有一种数据结构,ArrayList是动态数组,LinkedList是链表,HashMap/HashSet是...

1989
来自专栏我是东东强

常见算法之排序

各类排序算法,不仅是算法基本功,也是面试中永恒的考题,关于每种算法思想、实现(递归与非递归)以及时空复杂度分析是必须牢牢把握的送分题。本文先将排序算法按不同标准...

852

扫码关注云+社区