快速排序算法到底有多快？

今天來詳細剖析一下快速排序算法，看看到底快在哪里~

快速排序算法是最流行的排序算法，因為有充足的理由，在大多數(shù)情況下，快速排序都是最快的，執(zhí)行時間為O(NlogN)級（這只是對內部排序或者說隨機存儲器內的排序而言，對于在磁盤文件中的數(shù)據(jù)進行的排序，其他的排序算法可能更好）。快速排序本質上通過一個數(shù)組劃分為兩個子數(shù)組，然后遞歸地調用自身為每一個子數(shù)組進行快速排序來實現(xiàn)的，即算法分為三步：

今天來詳細剖析一下快速排序算法，看看到底快在哪里~

快速排序算法是最流行的排序算法，因為有充足的理由，在大多數(shù)情況下，快速排序都是最快的，執(zhí)行時間為O(NlogN)級（這只是對內部排序或者說隨機存儲器內的排序而言，對于在磁盤文件中的數(shù)據(jù)進行的排序，其他的排序算法可能更好）。快速排序本質上通過一個數(shù)組劃分為兩個子數(shù)組，然后遞歸地調用自身為每一個子數(shù)組進行快速排序來實現(xiàn)的，即算法分為三步：

1 把數(shù)組或者子數(shù)組劃分為左邊（較小的關鍵字）的一組和右邊（較大的關鍵字）的一組；

2 調用自身對左邊的一組進行排序；

3 調用自身對右邊的一組進行排序。

經(jīng)過一次劃分之后，所有在左邊子數(shù)組的數(shù)據(jù)項都小于在右邊子數(shù)組的數(shù)據(jù)項，只要對左邊子數(shù)組和右邊子數(shù)組分別進行排序，整個數(shù)組就是有序的了。下面試一次劃分后的示意圖：

快速排序需要劃分數(shù)組，這就用到了劃分算法。劃分算法是由兩個指針（這里是指數(shù)組數(shù)據(jù)項，非 C++ 中所說的指針）開始工作，兩個指針分別指向數(shù)組的兩頭，左邊的指針 leftPtr 向右移動，右邊的指針 rightPtr 向左移動。當 leftPtr 遇到比樞紐（待比較的數(shù)據(jù)項，比其小的在其左邊，比其大的在其右邊，下面均稱之為“樞紐”）小的數(shù)據(jù)項時繼續(xù)右移，當遇到比樞紐大的數(shù)據(jù)項時就停下來；類似的 rightPtr 想反。兩邊都停下后，leftPtr 和 rightPtr 都指在數(shù)組的錯誤一方的位置的數(shù)據(jù)項，交換這兩個數(shù)據(jù)項。交換后繼續(xù)移動這兩個指針。

基于上面的劃分算法，可以將數(shù)據(jù)快速排好序，下面是快速排序的實現(xiàn)代碼：

public?void?quickSort(int[] a)?{

recQuickSort(a,0, a.length-1);

}

public?void?recQuickSort(int[] a,?int?left,?int?right)?{

if(right-left <=?0) {

return;

}

else?{

int?pivot = a[right];?//保存最右邊的值，以這個值作為劃分點

int?partition = partitionIt(a,left, right, pivot);//將數(shù)組劃分兩部分，并將劃分點的值放在正確位置，并返回該位置

recQuickSort(a, left, partition-1);//調用自身對左邊進行排序

recQuickSort(a, partition+1, right);//調用自身對右邊進行排序

}

}

public?int?partitionIt(int[] a,?int?left,?int?right,?int?pivot)?{

int?leftPtr = left -?1;

int?rightPtr = right;

while(true) {

while(a[++leftPtr] < pivot){}?//往上找

while(rightPtr >?0?&& a[--rightPtr] > pivot){}?//往下找

if(leftPtr >= rightPtr)?break;

else?swap(leftPtr, rightPtr);

}

swap(leftPtr, right);//將劃分放在正確的位置

return?leftPtr;//返回劃分點，用于再次小范圍劃分

}

算法分析：快速排序是一種不穩(wěn)定的排序方法，其平均時間復雜度為 O(NlogN)，最壞的情況下退化成插入排序了，為 O(N^2)。

快速排序是不穩(wěn)定的，當 a=b>pivot 且 a 在 b 前面的時候，由于從后面開始遍歷，故 b 會先于 a 被替換到 pivot 的前面，這樣，b 就變成了在 a 的前面，也就是說，ab 位置對調，故該排序算法不穩(wěn)定。

空間復雜度平均為 O(logN)，空間復雜度主要是由于遞歸造成的。

在理想狀態(tài)下應該選擇被排序的數(shù)據(jù)項的中值數(shù)據(jù)項作為樞紐（上面程序中是用數(shù)組的最后一項作為樞紐的）。也就是說，應該有一半的數(shù)據(jù)項大于樞紐，一般的數(shù)據(jù)項小于樞紐。這會使數(shù)組被劃分成兩個大小相等的子數(shù)組。對于快速排序算法來說，擁有兩個大小相等的子數(shù)組是最優(yōu)的情況，最壞的情況就是一個子數(shù)組只有一個數(shù)據(jù)項，另一個子數(shù)組含有N-1個數(shù)據(jù)項。所以上面的算法中如果最右邊的數(shù)據(jù)是最小的或者最大的，那就可能導致最壞的情況出現(xiàn)。為了解決這個問題，我們可以改進上面的算法，使用“三數(shù)據(jù)項取中”劃分：找到數(shù)組里的第一個、最后一個以及中間位置數(shù)據(jù)項的值，將三個中處在中間大小的數(shù)據(jù)項作為樞紐，且將三個數(shù)排好序。下面是改進的快速排序：

public?void?quickSort2(int[] a)?{

recQuickSort2(a,?0, a.length-1);

}

public?void?recQuickSort2(int[] a,?int?left,?int?right)?{

int?size = right - left +?1;

if(size <=?3) {

manualSort(a, left, right);//數(shù)據(jù)項小于等于3個，直接排

}

else?{

long?median = medianOf3(a, left, right);//取左邊、右邊和中間三個數(shù)中中等大小的數(shù)作為樞紐

int?partition = partitionIt2(a, left, right, median);//將樞紐放到正確的位置

recQuickSort2(a, left, partition-1);//調用自身對左邊進行排序

recQuickSort2(a, partition+1, right);//調用自身對右邊進行排序

}

}

private?void?manualSort(int[] a,?int?left,?int?right)?{

int?size = right - left +?1;

if(size <=?1) {

return;?//1個不用排

}

if(size ==?2) {

if(a[left] > a[right]) {?//2個很好排

swap(left, right);

}

return;

}

else?{?//3個比較下就可以排好了

int?center = right -?1;

if(a[left] > a[center]) {

swap(left, center);

}

if(a[left] > a[right]) {

swap(left, right);

}

if(a[center] > a[right]) {

swap(center, right);

}

}

}

private?long?medianOf3(int[] a,?int?left,?int?right)?{

int?center = (left + right) /?2;

if(a[left] > a[center]) {

swap(left, center);

}

if(a[left] > a[right]) {

swap(left, right);

}

if(a[center] > a[right]) {

swap(center, right);

}//已經(jīng)將三個排好序

swap(center, right -?1);?//然后將樞紐保存在right-1位置

return?a[right-1];//這保證了首位置比樞紐值小，最末尾位置比樞紐值大

}

public?int?partitionIt2(int[] a,?int?left,?int?right,?long?pivot)?{

int?leftPtr = left;

int?rightPtr = right -?1;

while(true) {

while(a[++leftPtr] < pivot){}?//往上找

while(a[--rightPtr] > pivot){}?//往下找

if(leftPtr >= rightPtr)?break;

else?swap(leftPtr, rightPtr);

}

swap(leftPtr, right-1);//把right-1處存放的樞紐放到正確位置

return?leftPtr;//返回劃分點，用于再次小范圍劃分

}

算法分析：三數(shù)據(jù)項取中法除了對選擇樞紐更為有效外，還有另一個好處：可以對第二個內部 while 循環(huán)中取消 rightPtr>left（即 rightPtr>0）的測試，以略微提高算法的執(zhí)行速度。因為在選擇的過程中使用三數(shù)據(jù)項取中法不僅選擇了樞紐，而且對這三個數(shù)據(jù)項進行了排序，所以就可以保證數(shù)組最左端的數(shù)據(jù)項小于或者等于樞紐，最右端的數(shù)據(jù)項大于或者等于樞紐，所以就可以省去 rightPtr<0 的檢測了，leftPtr 和 rightPtr 不會分別越過數(shù)組的最右端或者最左端。

三數(shù)據(jù)項取中還有一個小的好處是，對左端、中間以及右端的數(shù)據(jù)項排序后，劃分過程就不需要再考慮這三個數(shù)據(jù)項了，所以上面的程序中左端真正是從 left+1 處開始的，右端真正是從 right-2 處開始的（因為 right 處存的是比樞紐大的數(shù)據(jù)項，right-1 處存的是樞紐）。

如果使用三數(shù)據(jù)項取中劃分方法，則必須要遵循快速排序算法不能執(zhí)行三個或者少于三個項的劃分規(guī)則。在這種情況下，數(shù)字3被稱為切割點(cutoff)。在上面的例子中，我們用一段代碼手動對兩個或三個數(shù)據(jù)項的子數(shù)組來排序的，但是這不是最好的方法。

處理小劃分的另一個選擇是使用插入排序。當使用插入排序的時候，不以限制3為切割點，可以把界限定位10、20或者其他任何數(shù)，試驗不同切割點的值找到最好的執(zhí)行效率是很有意義的。最好的選擇值取決于計算機、操作系統(tǒng)、編譯器等。這里使用9作為切割點。也就是說，當待比較的數(shù)小于等于9時，我們使用插入排序，大于9時我們使用快速排序法。繼續(xù)修改上面的程序：

public?void?quickSort3(int[] a)?{

recQuickSort3(a,?0, a.length-1);

}

public?void?recQuickSort3(int[] a,?int?left,?int?right)?{

int?size = right - left +?1;

if(size

insertionSort(a, left, right);//小于10項使用插入排序

}

else?{?//大于10項使用快速排序

long?median = medianOf3(a, left, right);

int?partition = partitionIt2(a, left, right, median);//上面的partionIt2方法

recQuickSort3(a, left, partition-1);

recQuickSort3(a, partition+1, right);

}

}

private?void?insertionSort(int[] a,?int?left,?int?right)?{

for(int?i = left +?1; i <= right; i++) {

for(int?j = i; (j > left) && (a[j] < a[j-1]); j--) {

swap(j, j-1);

}

}

}

經(jīng)過兩次改進后，這樣快速排序便結合了插入排序，三數(shù)據(jù)項取中法等方法，算是比較好的一個算法了。

HTTP

版權聲明：本文內容由網(wǎng)絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內刪除侵權內容。

版權聲明：本文內容由網(wǎng)絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內刪除侵權內容。