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
相关阅读: