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