PHP排序算法之快速排序(Quick Sort)及其优化算法

发布:smiling　来源: PHP粉丝网　添加日期：2018-11-04 13:47:31　浏览: 评论：0　

本文实例讲述了PHP排序算法之快速排序(Quick Sort)及其优化算法。分享给大家供大家参考，具体如下：

基本思想：

快速排序（Quicksort）是对冒泡排序的一种改进。他的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行快速排序，整个排序过程可以递归进行，以达到整个序列有序的目的。

基本算法步骤：

举个栗子：

假如现在待排序记录是：

6 2 7 3 8 9

第一步、创建变量 $low 指向记录中的第一个记录，$high 指向最后一个记录，$pivot 作为枢轴赋值为待排序记录的第一个元素（不一定是第一个），这里：

$low = 0;

$high = 5;

$pivot = 6;

第二步、我们要把所有比 $pivot 小的数移动到 $pivot 的左面，所以我们可以开始寻找比6小的数，从 $high 开始，从右往左找，不断递减变量 $high 的值，我们找到第一个下标 3 的数据比 6 小，于是把数据 3 移到下标 0 的位置（$low 指向的位置），把下标 0 的数据 6 移到下标 3，完成第一次比较：

3 2 7 6 8 9

//这时候,$high 减小为 3

$low = 0;

$high = 3;

$pivot = 6;

第三步、我们开始第二次比较，这次要变成找比 $pivot 大的了，而且要从前往后找了。递加变量 $low，发现下标 2 的数据是第一个比 $pivot 大的，于是用下标 2 （$low 指向的位置）的数据 7 和指向的下标 3 （$high 指向的位置）的数据的 6 做交换，数据状态变成下表：

3 2 6 7 8 9

//这时候,$high 减小为 3

$low = 2;

$high = 3;

$pivot = 6;

完成第二步和第三步我们称为完成一个循环。

第四步（也就是开启下一个循环）、模仿第二步的过程执行。

第五步、模仿第三步的过程执行。

执行完第二个循环之后，数据状态如下：

3 2 6 7 8 9

//这时候,$high 减小为 3

$low = 2;

$high = 2;

$pivot = 6;

到了这一步，我们发现 $low 和 $high“碰头”了：他们都指向了下标 2。于是，第一遍比较结束。得到结果如下，凡是 $pivot(=6) 左边的数都比它小，凡是 $pivot 右边的数都比它大。

然后，对、$pivot 两边的数据 {3，2} 和 {7，8，9}，再分组分别进行上述的过程，直到不能再分组为止。

注意：第一遍快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。

算法实现：

//交换函数

function swap(array &$arr,$a,$b){

  $temp = $arr[$a];

  $arr[$a] = $arr[$b];

  $arr[$b] = $temp;

}

//主函数：

function QuickSort(array &$arr){

  $low = 0;

  $high = count($arr) - 1;

  QSort($arr,$low,$high);

}

主函数中，由于第一遍快速排序是对整个数组排序的，因此开始是 $low=0,$high=count($arr)-1。

然后 QSort() 函数是个递归调用过程，因此对它封装了一下：

function QSort(array &$arr,$low,$high){

  //当 $low >= $high 时表示不能再进行分组，已经能够得出正确结果了

  if($low < $high){

    $pivot = Partition($arr,$low,$high); //将$arr[$low...$high]一分为二，算出枢轴值

    QSort($arr,$low,$pivot - 1); //对低子表（$pivot左边的记录）进行递归排序

    QSort($arr,$pivot + 1,$high); //对高子表（$pivot右边的记录）进行递归排序

  }

}

从上面的 QSort()函数中我们看出，Partition()函数才是整段代码的核心，因为该函数的功能是：选取当中的一个关键字，比如选择第一个关键字。然后想尽办法将它放到某个位置，使得它左边的值都比它小，右边的值都比它大，我们将这样的关键字成为枢轴（pivot）。

直接上代码：

//选取数组当中的一个关键字，使得它处于数组某个位置时，左边的值比它小，右边的值比它大，该关键字叫做枢轴

//使枢轴记录到位，并返回其所在位置

function Partition(array &$arr,$low,$high){

  $pivot = $arr[$low];  //选取子数组第一个元素作为枢轴

  while($low < $high){ //从数组的两端交替向中间扫描（当 $low 和 $high 碰头时结束循环）

    while($low < $high && $arr[$high] >= $pivot){

      $high --;

    }

    swap($arr,$low,$high); //终于遇到一个比$pivot小的数，将其放到数组低端

    while($low < $high && $arr[$low] <= $pivot){

      $low ++;

    }

    swap($arr,$low,$high); //终于遇到一个比$pivot大的数，将其放到数组高端

  }

  return $low;  //返回high也行，毕竟最后low和high都是停留在pivot下标处

}

组合起来的整个代码如下：

function swap(array &$arr,$a,$b){

  $temp = $arr[$a];

  $arr[$a] = $arr[$b];

  $arr[$b] = $temp;

}

function Partition(array &$arr,$low,$high){

  $pivot = $arr[$low];  //选取子数组第一个元素作为枢轴

  while($low < $high){ //从数组的两端交替向中间扫描

    while($low < $high && $arr[$high] >= $pivot){

      $high --;

    }

    swap($arr,$low,$high); //终于遇到一个比$pivot小的数，将其放到数组低端

    while($low < $high && $arr[$low] <= $pivot){

      $low ++;

    }

    swap($arr,$low,$high); //终于遇到一个比$pivot大的数，将其放到数组高端

  }

  return $low;  //返回high也行，毕竟最后low和high都是停留在pivot下标处

}

function QSort(array &$arr,$low,$high){

  if($low < $high){

    $pivot = Partition($arr,$low,$high); //将$arr[$low...$high]一分为二，算出枢轴值

    QSort($arr,$low,$pivot - 1);  //对低子表进行递归排序

    QSort($arr,$pivot + 1,$high); //对高子表进行递归排序

  }//phpfensi.com

}

function QuickSort(array &$arr){

  $low = 0;

  $high = count($arr) - 1;

  QSort($arr,$low,$high);

}

我们调用算法：

$arr = array(9,1,5,8,3,7,4,6,2);

QuickSort($arr);

var_dump($arr);

运行结果：

array(9) {

[0]=>

int(1)

[1]=>

int(2)

[2]=>

int(3)

[3]=>

int(4)

[4]=>

int(5)

[5]=>

int(6)

[6]=>

int(7)

[7]=>

int(8)

[8]=>

int(9)

}

复杂度分析：

在最优的情况下，也就是选择数轴处于整个数组的中间值的话，则每一次就会不断将数组平分为两半。因此最优情况下的时间复杂度是 O(nlogn) （跟堆排序、归并排序一样）。

最坏的情况下，待排序的序列是正序或逆序的，那么在选择枢轴的时候只能选到边缘数据，每次划分得到的比上一次划分少一个记录，另一个划分为空，这样的情况的最终时间复杂度为 O(n^2).

综合最优与最差情况，平均的时间复杂度是 O(nlogn).

快速排序是一种不稳定排序方法。

由于快速排序是个比较高级的排序，而且被列为20世纪十大算法之一。。。。如此牛掰的算法，我们还有什么理由不去学他呢！

尽管这个算法已经很牛掰了，但是上面的算法程序依然有改进的地方，下面具体讨论一下

快速排序算法优化

优化一：优化选取枢轴：

在前面的复杂度分析的过程中，我们看到最坏的情况无非就是当我们选中的枢轴是整个序列的边缘值。比如这么一个序列：

9 1 5 8 3 7 4 6 2

按照习惯我们选择数组的第一个元素作为枢轴，则 $pivot = 9，在一次循环下来后划分为{1，5，8，3，7，4，6，2} 和{ }（空序列），也就是每一次划分只得到少一个记录的子序列，而另一个子序列为空。最终时间复杂度为 O(n^2)。最优的情况是当我们选中的枢轴是整个序列的中间值。但是我们不能每次都去遍历数组拿到最优值吧？那么就有了一下解决方法：

1、随机选取：随机选取 $low 到 $high 之间的数值，但是这样的做法有些撞大运的感觉了，万一没撞成功呢，那上面的问题还是没有解决。

2、三数取中法：取三个关键字先进行排序，取出中间数作为枢轴。这三个数一般取最左端、最右端和中间三个数，也可以随机取三个数。这样的取法得到的枢轴为中间数的可能性就大大提高了。由于整个序列是无序的，随机选择三个数和从左中右端取出三个数其实就是同一回事。而且随机数生成器本身还会带来时间的开销，因此随机生成不予考虑。

出于这个想法，我们修改 Partition() 函数：

function Partition(array &$arr,$low,$high){

  $mid = floor($low + ($high - $low) / 2);  //计算数组中间的元素的下标

  if($arr[$low] > $arr[$high]){

    swap($arr,$low,$high);

  }

  if($arr[$mid] > $arr[$high]){

    swap($arr,$mid,$high);

  }

  if($arr[$low] < $arr[$mid]){

    swap($arr,$low,$mid);

  }

  //经过上面三步之后，$arr[$low]已经成为整个序列左中右端三个关键字的中间值

  $pivot = $arr[$low];

  while($low < $high){  //从数组的两端交替向中间扫描（当 $low 和 $high 碰头时结束循环）

    while($low < $high && $arr[$high] >= $pivot){

      $high --;

    }

    swap($arr,$low,$high); //终于遇到一个比$pivot小的数，将其放到数组低端

    while($low < $high && $arr[$low] <= $pivot){

      $low ++;

    }

    swap($arr,$low,$high); //终于遇到一个比$pivot大的数，将其放到数组高端

  }

  return $low;  //返回high也行，毕竟最后low和high都是停留在pivot下标处

}

三数取中法对于小数组有很大可能能沟得出比较理想的 $pivot，但是对于大数组就未必了，因此还有个办法是九数取中法。。。。。。

优化二：优化不必要的交换：

现在假如有个待排序的序列如下：

5 1 9 3 7 4 8 6 2

根据三数取中法我们取 5 7 2 中的 5 作为枢轴。

当你按照快速排序算法走一个循环，你会发现 5 的下标变换顺序是这样的：0 -> 8 -> 2 -> 5 -> 4，但是它的最终目标就是 4 的位置，当中的交换其实是不需要的。

根据这个思想，我们改进我们的 Partition() 函数:

function Partition(array &$arr,$low,$high){

  $mid = floor($low + ($high - $low) / 2);  //计算数组中间的元素的下标

  if($arr[$low] > $arr[$high]){

    swap($arr,$low,$high);

  }

  if($arr[$mid] > $arr[$high]){

    swap($arr,$mid,$high);

  }

  if($arr[$low] < $arr[$mid]){

    swap($arr,$low,$mid);

  }

  //经过上面三步之后，$arr[$low]已经成为整个序列左中右端三个关键字的中间值

  $pivot = $arr[$low];

  $temp = $pivot;

  while($low < $high){  //从数组的两端交替向中间扫描（当 $low 和 $high 碰头时结束循环）

    while($low < $high && $arr[$high] >= $pivot){

      $high --;

    }

    //swap($arr,$low,$high); //终于遇到一个比$pivot小的数，将其放到数组低端

    $arr[$low] = $arr[$high];  //使用替换而不是交换的方式进行操作

    while($low < $high && $arr[$low] <= $pivot){

      $low ++;

    }

    //swap($arr,$low,$high); //终于遇到一个比$pivot大的数，将其放到数组高端

    $arr[$high] = $arr[$low];

  }//phpfensi.com

  $arr[$low] = $temp;  //将枢轴数值替换回 $arr[$low];

  return $low;  //返回high也行，毕竟最后low和high都是停留在pivot下标处

}

在上面的改进中，我们使用替换而不是交进行操作，由于在这当中少了多次的数据交换，因此在性能上也是有所提高的。

优化三：优化小数组的排序方案：

对于一个数学科学家、博士生导师，他可以攻克世界性的难题，可以培育最优秀的数学博士，当让他去教小学生“1 + 1 = 2”的算术课程，那还真未必比常年在小学里耕耘的数学老师教的好。换句话说，大材小用有时会变得反而不好用。

也就是说，快速排序对于比较大数组来说是一个很好的排序方案，但是假如数组非常小，那么快速排序算法反而不如直接插入排序来得更好（直接插入排序是简单排序中性能最好的）。其原因在于快速排序用到了递归操作，在大量数据排序的时候，这点性能影响相对于它的整体算法优势而言是可以忽略的，但如果数组只有几个记录需要排序时，这就成了大炮打蚊子的大问题。

因此我们需要修改一下我们的 QSort() 函数：

//规定数组长度阀值

#define MAX_LENGTH_INSERT_SORT 7

function QSort(array &$arr,$low,$high){

  //当 $low >= $high 时表示不能再进行分组，已经能够得出正确结果了

  if(($high - $low) > MAX_LENGTH_INSERT_SORT){

    $pivot = Partition($arr,$low,$high); //将$arr[$low...$high]一分为二，算出枢轴值

    QSort($arr,$low,$pivot - 1); //对低子表（$pivot左边的记录）进行递归排序

    QSort($arr,$pivot + 1,$high); //对高子表（$pivot右边的记录）进行递归排序

  }else{

    //直接插入排序

    InsertSort($arr);

  }

}

PS：上面的直接插入排序算法大家可以参考：《PHP排序算法之直接插入排序（Straight Insertion Sort）》

在这里我们增加一个判断，当 $high - $low 不大于一个常数时（有资料认为 7 比较合适，也有认为 50 比较合适，实际情况可以是适当调整），就用直接插入排序，这样就能保证最大化的利用这两种排序的优势来完成排序工作。

优化四：优化递归操作：

大家知道，递归对性能时有一定影响的，QSort()函数在其尾部有两次递归的操作，如果待排序的序列划分极端不平衡（就是我们在选择枢轴的时候不是中间值），那么递归的深度将趋近于 n，而不是平衡时的 log₂n，这就不仅仅是速度快慢的问题了。

我们也知道，递归是通过栈来实现的，栈的大小是很有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多，因此如果能减少队规，将会大大提高性能。

听说，递归都可以改造成循环实现。我们在这里就是使用循环去优化递归。（关于递归与循环大家可以参考知乎里面的讨论《所有递归都可以改写成循环吗？》）

我们对QSort() 函数尾部递归进行优化：

//规定数组长度阀值

#define MAX_LENGTH_INSERT_SORT 7

function QSort(array &$arr,$low,$high){

  //当 $low >= $high 时表示不能再进行分组，已经能够得出正确结果了

  if(($high - $low) > MAX_LENGTH_INSERT_SORT){

    while($low < $high){

      $pivot = Partition($arr,$low,$high); //将$arr[$low...$high]一分为二，算出枢轴值

      QSort($arr,$low,$pivot - 1); //对低子表（$pivot左边的记录）进行递归排序

      $low = $pivot + 1;

    }

  }else{

    //直接插入排序

    InsertSort($arr);

  }

}