PHP排序演算法之快速排序(Quick Sort)及其最佳化

這篇文章主要介紹了PHP排序演算法之快速排序(Quick Sort)及其優化演算法,結合實例形式分析了php快速排序的原理、實現方法,並分析了各種優化技巧與操作注意事項,需要的朋友可以參考下

本文實例講述了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); //对高子表进行递归排序
  }
}
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];
  }
  $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);
  }
}

在上面，我们使用循环替换递归，减少了之前一般的递归量。结果是一样的，但是采用循环而不是递归的方法可以缩减堆栈的深度，从而提高了整体性能。

相关推荐：

PHP排序算法之归并排序(Merging Sort)

PHP排序算法之冒泡排序(Bubble Sort)

PHP排序算法之简单选择排序(Simple Selection Sort)

以上是PHP排序演算法之快速排序(Quick Sort)及其最佳化的詳細內容。更多資訊請關注PHP中文網其他相關文章！