PHP排序算法之快速排序(Quick Sort)及其優(yōu)化算法詳解

本文實(shí)例講述了PHP排序算法之快速排序(Quick Sort)及其優(yōu)化算法。分享給大家供大家參考，具體如下：

基本思想：

快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)。他的基本思想是：通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以達(dá)到整個(gè)序列有序的目的。

基本算法步驟：

舉個(gè)栗子：

假如現(xiàn)在待排序記錄是：

6   2   7   3   8   9

第一步、創(chuàng)建變量 $low 指向記錄中的第一個(gè)記錄，$high 指向最后一個(gè)記錄，$pivot 作為樞軸賦值為待排序記錄的第一個(gè)元素（不一定是第一個(gè)），這里：

$low = 0;
$high = 5;
$pivot = 6;

第二步、我們要把所有比 $pivot 小的數(shù)移動(dòng)到 $pivot 的左面，所以我們可以開始尋找比6小的數(shù)，從 $high 開始，從右往左找，不斷遞減變量 $high 的值，我們找到第一個(gè)下標(biāo) 3 的數(shù)據(jù)比 6 小，于是把數(shù)據(jù) 3 移到下標(biāo) 0 的位置（$low 指向的位置），把下標(biāo) 0 的數(shù)據(jù) 6 移到下標(biāo) 3，完成第一次比較：

3   2   7   6   8   9

//這時(shí)候,$high 減小為 3
$low = 0;
$high = 3;
$pivot = 6;

第三步、我們開始第二次比較，這次要變成找比 $pivot 大的了，而且要從前往后找了。遞加變量 $low，發(fā)現(xiàn)下標(biāo) 2 的數(shù)據(jù)是第一個(gè)比 $pivot 大的，于是用下標(biāo) 2 （$low 指向的位置）的數(shù)據(jù) 7 和 指向的下標(biāo) 3 （$high 指向的位置）的數(shù)據(jù)的 6 做交換，數(shù)據(jù)狀態(tài)變成下表：

3   2   6   7   8   9

//這時(shí)候,$high 減小為 3
$low = 2;
$high = 3;
$pivot = 6;

完成第二步和第三步我們稱為完成一個(gè)循環(huán)。

第四步（也就是開啟下一個(gè)循環(huán)）、模仿第二步的過(guò)程執(zhí)行。

第五步、模仿第三步的過(guò)程執(zhí)行。

執(zhí)行完第二個(gè)循環(huán)之后，數(shù)據(jù)狀態(tài)如下：

3   2   6   7   8   9

//這時(shí)候,$high 減小為 3
$low = 2;
$high = 2;
$pivot = 6;

到了這一步，我們發(fā)現(xiàn) $low 和 $high“碰頭”了：他們都指向了下標(biāo) 2。于是，第一遍比較結(jié)束。得到結(jié)果如下，凡是 $pivot(=6) 左邊的數(shù)都比它小，凡是 $pivot 右邊的數(shù)都比它大。

然后，對(duì) 、$pivot 兩邊的數(shù)據(jù) {3，2} 和 {7，8，9}，再分組分別進(jìn)行上述的過(guò)程，直到不能再分組為止。

注意：第一遍快速排序不會(huì)直接得到最終結(jié)果，只會(huì)把比k大和比k小的數(shù)分到k的兩邊。為了得到最后結(jié)果，需要再次對(duì)下標(biāo)2兩邊的數(shù)組分別執(zhí)行此步驟，然后再分解數(shù)組，直到數(shù)組不能再分解為止（只有一個(gè)數(shù)據(jù)），才能得到正確結(jié)果。

算法實(shí)現(xiàn)：

//交換函數(shù)
function swap(array $arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//主函數(shù)：
function QuickSort(array $arr){
  $low = 0;
  $high = count($arr) - 1;
  QSort($arr,$low,$high);
}

主函數(shù)中，由于第一遍快速排序是對(duì)整個(gè)數(shù)組排序的，因此開始是 $low=0,$high=count($arr)-1。

然后 QSort() 函數(shù)是個(gè)遞歸調(diào)用過(guò)程，因此對(duì)它封裝了一下：

function QSort(array $arr,$low,$high){
  //當(dāng) $low >= $high 時(shí)表示不能再進(jìn)行分組，已經(jīng)能夠得出正確結(jié)果了
  if($low  $high){
    $pivot = Partition($arr,$low,$high); //將$arr[$low...$high]一分為二，算出樞軸值
    QSort($arr,$low,$pivot - 1); //對(duì)低子表（$pivot左邊的記錄）進(jìn)行遞歸排序
    QSort($arr,$pivot + 1,$high); //對(duì)高子表（$pivot右邊的記錄）進(jìn)行遞歸排序
  }
}

從上面的 QSort()函數(shù)中我們看出，Partition()函數(shù)才是整段代碼的核心，因?yàn)樵摵瘮?shù)的功能是：選取當(dāng)中的一個(gè)關(guān)鍵字，比如選擇第一個(gè)關(guān)鍵字。然后想盡辦法將它放到某個(gè)位置，使得它左邊的值都比它小，右邊的值都比它大，我們將這樣的關(guān)鍵字成為樞軸（pivot）。

直接上代碼：

//選取數(shù)組當(dāng)中的一個(gè)關(guān)鍵字，使得它處于數(shù)組某個(gè)位置時(shí)，左邊的值比它小，右邊的值比它大，該關(guān)鍵字叫做樞軸
//使樞軸記錄到位，并返回其所在位置
function Partition(array $arr,$low,$high){
  $pivot = $arr[$low];  //選取子數(shù)組第一個(gè)元素作為樞軸
  while($low  $high){ //從數(shù)組的兩端交替向中間掃描（當(dāng) $low 和 $high 碰頭時(shí)結(jié)束循環(huán)）
    while($low  $high  $arr[$high] >= $pivot){
      $high --;
    }
    swap($arr,$low,$high); //終于遇到一個(gè)比$pivot小的數(shù)，將其放到數(shù)組低端
    while($low  $high  $arr[$low] = $pivot){
      $low ++;
    }
    swap($arr,$low,$high); //終于遇到一個(gè)比$pivot大的數(shù)，將其放到數(shù)組高端
  }
  return $low;  //返回high也行，畢竟最后low和high都是停留在pivot下標(biāo)處
}

組合起來(lái)的整個(gè)代碼如下：

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];  //選取子數(shù)組第一個(gè)元素作為樞軸
  while($low  $high){ //從數(shù)組的兩端交替向中間掃描
    while($low  $high  $arr[$high] >= $pivot){
      $high --;
    }
    swap($arr,$low,$high); //終于遇到一個(gè)比$pivot小的數(shù)，將其放到數(shù)組低端
    while($low  $high  $arr[$low] = $pivot){
      $low ++;
    }
    swap($arr,$low,$high); //終于遇到一個(gè)比$pivot大的數(shù)，將其放到數(shù)組高端
  }
  return $low;  //返回high也行，畢竟最后low和high都是停留在pivot下標(biāo)處
}
function QSort(array $arr,$low,$high){
  if($low  $high){
    $pivot = Partition($arr,$low,$high); //將$arr[$low...$high]一分為二，算出樞軸值
    QSort($arr,$low,$pivot - 1);  //對(duì)低子表進(jìn)行遞歸排序
    QSort($arr,$pivot + 1,$high); //對(duì)高子表進(jìn)行遞歸排序
  }
}
function QuickSort(array $arr){
  $low = 0;
  $high = count($arr) - 1;
  QSort($arr,$low,$high);
}

我們調(diào)用算法：

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

運(yùn)行結(jié)果：

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)
}

復(fù)雜度分析：

在最優(yōu)的情況下，也就是選擇數(shù)軸處于整個(gè)數(shù)組的中間值的話，則每一次就會(huì)不斷將數(shù)組平分為兩半。因此最優(yōu)情況下的時(shí)間復(fù)雜度是 O(nlogn) （跟堆排序、歸并排序一樣）。

最壞的情況下，待排序的序列是正序或逆序的，那么在選擇樞軸的時(shí)候只能選到邊緣數(shù)據(jù)，每次劃分得到的比上一次劃分少一個(gè)記錄，另一個(gè)劃分為空，這樣的情況的最終時(shí)間復(fù)雜度為 O(n^2).

綜合最優(yōu)與最差情況，平均的時(shí)間復(fù)雜度是 O(nlogn).

快速排序是一種不穩(wěn)定排序方法。

由于快速排序是個(gè)比較高級(jí)的排序，而且被列為20世紀(jì)十大算法之一。。。。如此牛掰的算法，我們還有什么理由不去學(xué)他呢！

盡管這個(gè)算法已經(jīng)很牛掰了，但是上面的算法程序依然有改進(jìn)的地方，下面具體討論一下

快速排序算法優(yōu)化

優(yōu)化一：優(yōu)化選取樞軸：

在前面的復(fù)雜度分析的過(guò)程中，我們看到最壞的情況無(wú)非就是當(dāng)我們選中的樞軸是整個(gè)序列的邊緣值。比如這么一個(gè)序列：

9   1   5   8   3   7   4   6   2

按照習(xí)慣我們選擇數(shù)組的第一個(gè)元素作為樞軸，則 $pivot = 9，在一次循環(huán)下來(lái)后劃分為{1，5，8，3，7，4，6，2} 和{ }（空序列），也就是每一次劃分只得到少一個(gè)記錄的子序列，而另一個(gè)子序列為空。最終時(shí)間復(fù)雜度為 O(n^2)。最優(yōu)的情況是當(dāng)我們選中的樞軸是整個(gè)序列的中間值。但是我們不能每次都去遍歷數(shù)組拿到最優(yōu)值吧？那么就有了一下解決方法：

1、隨機(jī)選?。弘S機(jī)選取 $low 到 $high 之間的數(shù)值，但是這樣的做法有些撞大運(yùn)的感覺(jué)了，萬(wàn)一沒(méi)撞成功呢，那上面的問(wèn)題還是沒(méi)有解決。

2、三數(shù)取中法：取三個(gè)關(guān)鍵字先進(jìn)行排序，取出中間數(shù)作為樞軸。這三個(gè)數(shù)一般取最左端、最右端和中間三個(gè)數(shù)，也可以隨機(jī)取三個(gè)數(shù)。這樣的取法得到的樞軸為中間數(shù)的可能性就大大提高了。由于整個(gè)序列是無(wú)序的，隨機(jī)選擇三個(gè)數(shù)和從左中右端取出三個(gè)數(shù)其實(shí)就是同一回事。而且隨機(jī)數(shù)生成器本身還會(huì)帶來(lái)時(shí)間的開銷，因此隨機(jī)生成不予考慮。

出于這個(gè)想法，我們修改 Partition() 函數(shù)：

function Partition(array $arr,$low,$high){
  $mid = floor($low + ($high - $low) / 2);  //計(jì)算數(shù)組中間的元素的下標(biāo)
  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);
  }
  //經(jīng)過(guò)上面三步之后，$arr[$low]已經(jīng)成為整個(gè)序列左中右端三個(gè)關(guān)鍵字的中間值
  $pivot = $arr[$low];
  while($low  $high){  //從數(shù)組的兩端交替向中間掃描（當(dāng) $low 和 $high 碰頭時(shí)結(jié)束循環(huán)）
    while($low  $high  $arr[$high] >= $pivot){
      $high --;
    }
    swap($arr,$low,$high); //終于遇到一個(gè)比$pivot小的數(shù)，將其放到數(shù)組低端
    while($low  $high  $arr[$low] = $pivot){
      $low ++;
    }
    swap($arr,$low,$high); //終于遇到一個(gè)比$pivot大的數(shù)，將其放到數(shù)組高端
  }
  return $low;  //返回high也行，畢竟最后low和high都是停留在pivot下標(biāo)處
}

三數(shù)取中法對(duì)于小數(shù)組有很大可能能溝得出比較理想的 $pivot，但是對(duì)于大數(shù)組就未必了，因此還有個(gè)辦法是九數(shù)取中法。。。。。。

優(yōu)化二：優(yōu)化不必要的交換：

現(xiàn)在假如有個(gè)待排序的序列如下：

5   1   9   3   7   4   8   6   2

根據(jù)三數(shù)取中法我們?nèi)?5 7 2 中的 5 作為樞軸。

當(dāng)你按照快速排序算法走一個(gè)循環(huán)，你會(huì)發(fā)現(xiàn) 5 的下標(biāo)變換順序是這樣的：0 -> 8 -> 2 -> 5 -> 4，但是它的最終目標(biāo)就是 4 的位置，當(dāng)中的交換其實(shí)是不需要的。

根據(jù)這個(gè)思想，我們改進(jìn)我們的 Partition() 函數(shù):

function Partition(array $arr,$low,$high){
  $mid = floor($low + ($high - $low) / 2);  //計(jì)算數(shù)組中間的元素的下標(biāo)
  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);
  }
  //經(jīng)過(guò)上面三步之后，$arr[$low]已經(jīng)成為整個(gè)序列左中右端三個(gè)關(guān)鍵字的中間值
  $pivot = $arr[$low];
  $temp = $pivot;
  while($low  $high){  //從數(shù)組的兩端交替向中間掃描（當(dāng) $low 和 $high 碰頭時(shí)結(jié)束循環(huán)）
    while($low  $high  $arr[$high] >= $pivot){
      $high --;
    }
    //swap($arr,$low,$high); //終于遇到一個(gè)比$pivot小的數(shù)，將其放到數(shù)組低端
    $arr[$low] = $arr[$high];  //使用替換而不是交換的方式進(jìn)行操作
    while($low  $high  $arr[$low] = $pivot){
      $low ++;
    }
    //swap($arr,$low,$high); //終于遇到一個(gè)比$pivot大的數(shù)，將其放到數(shù)組高端
    $arr[$high] = $arr[$low];
  }
  $arr[$low] = $temp;  //將樞軸數(shù)值替換回 $arr[$low];
  return $low;  //返回high也行，畢竟最后low和high都是停留在pivot下標(biāo)處
}

在上面的改進(jìn)中，我們使用替換而不是交進(jìn)行操作，由于在這當(dāng)中少了多次的數(shù)據(jù)交換，因此在性能上也是有所提高的。

優(yōu)化三：優(yōu)化小數(shù)組的排序方案：

對(duì)于一個(gè)數(shù)學(xué)科學(xué)家、博士生導(dǎo)師，他可以攻克世界性的難題，可以培育最優(yōu)秀的數(shù)學(xué)博士，當(dāng)讓他去教小學(xué)生“1 + 1 = 2”的算術(shù)課程，那還真未必比常年在小學(xué)里耕耘的數(shù)學(xué)老師教的好。換句話說(shuō)，大材小用有時(shí)會(huì)變得反而不好用。

也就是說(shuō)，快速排序?qū)τ诒容^大數(shù)組來(lái)說(shuō)是一個(gè)很好的排序方案，但是假如數(shù)組非常小，那么快速排序算法反而不如直接插入排序來(lái)得更好（直接插入排序是簡(jiǎn)單排序中性能最好的）。其原因在于快速排序用到了遞歸操作，在大量數(shù)據(jù)排序的時(shí)候，這點(diǎn)性能影響相對(duì)于它的整體算法優(yōu)勢(shì)而言是可以忽略的，但如果數(shù)組只有幾個(gè)記錄需要排序時(shí)，這就成了大炮打蚊子的大問(wèn)題。

因此我們需要修改一下我們的 QSort() 函數(shù)：

//規(guī)定數(shù)組長(zhǎng)度閥值
#define MAX_LENGTH_INSERT_SORT 7
function QSort(array $arr,$low,$high){
  //當(dāng) $low >= $high 時(shí)表示不能再進(jìn)行分組，已經(jīng)能夠得出正確結(jié)果了
  if(($high - $low) > MAX_LENGTH_INSERT_SORT){
    $pivot = Partition($arr,$low,$high); //將$arr[$low...$high]一分為二，算出樞軸值
    QSort($arr,$low,$pivot - 1); //對(duì)低子表（$pivot左邊的記錄）進(jìn)行遞歸排序
    QSort($arr,$pivot + 1,$high); //對(duì)高子表（$pivot右邊的記錄）進(jìn)行遞歸排序
  }else{
    //直接插入排序
    InsertSort($arr);
  }
}

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

在這里我們?cè)黾右粋€(gè)判斷，當(dāng) $high - $low 不大于一個(gè)常數(shù)時(shí)（有資料認(rèn)為 7 比較合適，也有認(rèn)為 50 比較合適，實(shí)際情況可以是適當(dāng)調(diào)整），就用直接插入排序，這樣就能保證最大化的利用這兩種排序的優(yōu)勢(shì)來(lái)完成排序工作。

優(yōu)化四：優(yōu)化遞歸操作：

大家知道，遞歸對(duì)性能時(shí)有一定影響的，QSort()函數(shù)在其尾部有兩次遞歸的操作，如果待排序的序列劃分極端不平衡（就是我們?cè)谶x擇樞軸的時(shí)候不是中間值），那么遞歸的深度將趨近于 n，而不是平衡時(shí)的 log₂n，這就不僅僅是速度快慢的問(wèn)題了。

我們也知道，遞歸是通過(guò)棧來(lái)實(shí)現(xiàn)的，棧的大小是很有限的，每次遞歸調(diào)用都會(huì)耗費(fèi)一定的棧空間，函數(shù)的參數(shù)越多，每次遞歸耗費(fèi)的空間也越多，因此如果能減少隊(duì)規(guī)，將會(huì)大大提高性能。

聽說(shuō)，遞歸都可以改造成循環(huán)實(shí)現(xiàn)。我們?cè)谶@里就是使用循環(huán)去優(yōu)化遞歸。（關(guān)于遞歸與循環(huán)大家可以參考知乎里面的討論 《所有遞歸都可以改寫成循環(huán)嗎？》）

我們對(duì)QSort() 函數(shù)尾部遞歸進(jìn)行優(yōu)化：

//規(guī)定數(shù)組長(zhǎng)度閥值
#define MAX_LENGTH_INSERT_SORT 7
function QSort(array $arr,$low,$high){
  //當(dāng) $low >= $high 時(shí)表示不能再進(jìn)行分組，已經(jīng)能夠得出正確結(jié)果了
  if(($high - $low) > MAX_LENGTH_INSERT_SORT){
    while($low  $high){
      $pivot = Partition($arr,$low,$high); //將$arr[$low...$high]一分為二，算出樞軸值
      QSort($arr,$low,$pivot - 1); //對(duì)低子表（$pivot左邊的記錄）進(jìn)行遞歸排序
      $low = $pivot + 1;
    }
  }else{
    //直接插入排序
    InsertSort($arr);
  }
}

在上面，我們使用循環(huán)替換遞歸，減少了之前一般的遞歸量。結(jié)果是一樣的，但是采用循環(huán)而不是遞歸的方法可以縮減堆棧的深度，從而提高了整體性能。

好了、終于寫完了。這篇博客基本上是 Copy 《大話數(shù)據(jù)結(jié)構(gòu)》里面的內(nèi)容，在這里總結(jié)出來(lái)不僅是一個(gè)記錄，大家也可以從中獲得很大的收獲。

PS：這里再為大家推薦一款關(guān)于排序的演示工具供大家參考：

在線動(dòng)畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過(guò)程工具：
http://tools.jb51.net/aideddesign/paixu_ys

更多關(guān)于PHP相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《php排序算法總結(jié)》、《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《php程序設(shè)計(jì)算法總結(jié)》、《php字符串(string)用法總結(jié)》、《PHP數(shù)組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結(jié)》及《PHP數(shù)學(xué)運(yùn)算技巧總結(jié)》

希望本文所述對(duì)大家PHP程序設(shè)計(jì)有所幫助。