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 条评论
登录 后参与评论

相关文章

来自专栏java学习

重要通知!小编出新的Java练习题已经公布答案了!!!

一、选择题和问答题 1、在一个java原文件中,import, class, package语句的顺序是(D)。 A. import classpackage ...

3398
来自专栏专知

【专知-关关的刷题日记16】Leetcode 88. Merge Sorted Array

题目 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as on...

34410
来自专栏好好学java的技术栈

“365算法每日学计划”:java语言基础题目及解答(11-15打卡)

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。

571
来自专栏有趣的Python

6-玩转数据结构-二分搜索树

电脑中的文件夹就是一种树结构,计算机中让人们使用的存储结构来源于生活。图书馆分区,分类,分子类。

872
来自专栏老马说编程

(42) 排序二叉树 / 计算机程序的思维逻辑

40节介绍了HashMap,41节介绍了HashSet,它们的共同实现机制是哈希表,一个共同的限制是没有顺序,我们提到,它们都有一个能保持顺序的对应类TreeM...

1756
来自专栏数据结构与算法

1860 最大数

1860 最大数 1998年NOIP全国联赛提高组  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 白银 Silver 题解  查看运行...

2567
来自专栏恰同学骚年

数据结构基础温故-7.排序

排序(Sorting)是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为按关键字“有序”的记录序列。如何进行排序,特别是高效率地进行排序时计算...

511
来自专栏算法修养

树形DP总结,持续更新

自己做了动态规划的题目已经有了一个月,但是成效甚微,所以来总结一下动态规划,希望自己能够温故知新。这个博客是关于树形dp的,动态规划的一类题目。 ...

3675
来自专栏前端架构与工程

【译】《Understanding ECMAScript6》- 第一章-基础知识(一)

目录: 更好的Unicode编码支持 codePointAt()函数 String.fromCodePoint() 用转义序列对Non-BMP字符编码 nor...

2225
来自专栏前端布道

图解javascript this指向什么?

JavaScript 是一种脚本语言,支持函数式编程、闭包、基于原型的继承等高级功能。JavaScript一开始看起来感觉会很容易入门,但是随着使用的深入,你会...

3939

扫描关注云+社区