【46期】盤點那些必問的數(shù)據(jù)結(jié)構(gòu)算法題之快速排序

程序員的成長之路

互聯(lián)網(wǎng)/程序員/技術(shù)/資料共享?

閱讀本文大概需要 5 分鐘。

來自：juejin.im/post/5bae28e35188255c6f1e2bb1

0 概述

快速排序也是基于分治模式，類似歸并排序那樣，不同的是快速排序劃分最后不需要merge。對一個數(shù)組 A[p..r] 進行快速排序分為三個步驟：

• 劃分：數(shù)組 A[p…r] 被劃分為兩個子數(shù)組 A[p…q-1] 和 A[q+1…r]，使得 A[p…q-1] 中每個元素都小于等于 A[q]，而 A[q+1…r] 每個元素都大于 A[q]。劃分流程見下圖。

• 解決：通過遞歸調(diào)用快速排序，對子數(shù)組分別排序即可。

• 合并：因為兩個子數(shù)組都已經(jīng)排好序了，且已經(jīng)有大小關(guān)系了，不需要做任何操作。

快速排序算法不算復(fù)雜的算法，但是實際寫代碼的時候卻是最容易出錯的代碼，寫的不對就容易死循環(huán)或者劃分錯誤。

本文代碼見

https://github.com/shishujuan/dsalg/tree/master/code/alg/sort

1 樸素的快速排序

這個樸素的快速排序有個缺陷就是在一些極端情況如所有元素都相等時（或者元素本身有序，如 a[] = {1,2,3,4,5}等），樸素的快速算法時間復(fù)雜度為 O(N^2)，而如果能夠平衡劃分數(shù)組則時間復(fù)雜度為 O(NlgN)。

/**
?*?快速排序-樸素版本
?*/
void?quickSort(int?a[],?int?l,?int?u)
{
????if?(l?>=?u)?return;

????int?q?=?partition(a,?l,?u);
????quickSort(a,?l,?q-1);
????quickSort(a,?q+1,?u);
}

/**
?*?快速排序-劃分函數(shù)
?*/
int?partition(int?a[],?int?l,?int?u)
{
????int?i,?q=l;
????for?(i?=?l+1;?i?<=?u;?i++)?{
????????if?(a[i]?????????????swapInt(a,?i,?++q);
????}
????swapInt(a,?l,?q);
????return?q;
}

2 改進-雙向劃分的快速排序

一種改進方法就是采用雙向劃分，使用兩個變量 i 和 j，i 從左往右掃描，移過小元素，遇到大元素停止；j 從右往左掃描，移過大元素，遇到小元素停止。然后測試i和j是否交叉，如果交叉則停止，否則交換 i 與 j 對應(yīng)的元素值。

注意，如果數(shù)組中有相同的元素，則遇到相同的元素時，我們停止掃描，并交換 i 和 j 的元素值。雖然這樣交換次數(shù)增加了，但是卻將所有元素相同的最壞情況由 O(N^2) 變成了差不多 O(NlgN) 的情況。

比如數(shù)組 A={2,2,2,2,2}， 則使用樸素快速排序方法，每次都是劃分 n 個元素為 1 個和 n-1 個，時間復(fù)雜度為 O(N^2)，而使用雙向劃分后，第一次劃分的位置是 2，基本可以平衡劃分兩部分。

代碼如下：

/**
?*?快速排序-雙向劃分函數(shù)
?*/
int?partitionLR(int?a[],?int?l,?int?u,?int?pivot)
{
????int?i?=?l;
????int?j?=?u+1;
????while?(1)?{
????????do?{
????????????i++;
????????}?while?(a[i]?//注意i<=u這個判斷條件，不能越界。

????????do?{
????????????j--;
????????}?while?(a[j]?>?pivot);

????????if?(i?>?j)?break;

????????swapInt(a,?i,?j);
????}

????//?注意這里是交換l和j，而不是l和i，因為i與j交叉后，a[i...u]都大于等于樞紐元t，
????//?而樞紐元又在最左邊，所以不能與i交換。只能與j交換。
????swapInt(a,?l,?j);

????return?j;
}

/**
?*?快速排序-雙向劃分法
?*/
void?quickSortLR(int?a[],?int?l,?int?u)
{
????if?(l?>=?u)?return;

????int?pivot?=?a[l];
????int?q?=?partitionLR(a,?l,?u,?pivot);
????quickSortLR(a,?l,?q-1);
????quickSortLR(a,?q+1,?u);
}

雖然雙向劃分解決了所有元素相同的問題，但是對于一個已經(jīng)排好序的數(shù)組還是會達到 O(N^2) 的復(fù)雜度。此外，雙向劃分還要注意的一點是代碼中循環(huán)的寫法，如果寫成 while(a[i]

3 繼續(xù)改進—隨機法和三數(shù)取中法取樞紐元

為了解決上述問題，可以進一步改進，通過隨機選取樞紐元或三數(shù)取中方式來獲取樞紐元，然后進行雙向劃分。三數(shù)取中指的就是從數(shù)組A[l… u]中選擇左中右三個值進行排序，并使用中值作為樞紐元。

如數(shù)組 A[] = {1, 3, 5, 2, 4}，則我們對 A[0]、A[2]、A[4] 進行排序，選擇中值 A4 作為樞紐元，并將其交換到 a[l] ，最后數(shù)組變成 A[] = {4 3 5 2 1}，然后跟之前一樣雙向排序即可。

/**
?*?隨機選擇樞紐元
?*/
int?pivotRandom(int?a[],?int?l,?int?u)
{
????int?rand?=?randInt(l,?u);
????swapInt(a,?l,?rand);?//?交換樞紐元到位置l
????return?a[l];
}

/**
?*?三數(shù)取中選擇樞紐元
?*/
int?pivotMedian3(int?a[],?int?l,?int?u)
{
?????int?m?=?l?+?(u-l)/2;

?????/*
??????*?三數(shù)排序
??????*/
?????if(?a[l]?>?a[m]?)
????????swapInt(a,?l,?m);

?????if(?a[l]?>?a[u]?)
????????swapInt(a,?l,?u);

?????if(?a[m]?>?a[u]?)
????????swapInt(a,?m,?u);

?????/*?assert:?a[l]?<=?a[m]?<=?a[u]?*/
?????swapInt(a,?m,?l);?//?交換樞紐元到位置l

?????return?a[l];
}

此外，在數(shù)據(jù)基本有序的情況下，使用插入排序可以得到很好的性能，而且在排序很小的子數(shù)組時，插入排序比快速排序更快，可以在數(shù)組比較小時選用插入排序，而大數(shù)組才用快速排序。

4 非遞歸寫快速排序

非遞歸寫快速排序著實比較少見，不過練練手總是好的。需要用到棧，注意壓棧的順序。

代碼如下：

/**
?*?快速排序-非遞歸版本
?*/
void?quickSortIter(int?a[],?int?n)
{
????Stack?*stack?=?stackNew(n);
????int?l?=?0,?u?=?n-1;
????int?p?=?partition(a,?l,?u);

????if?(p-1?>?l)?{?//左半部分兩個邊界值入棧
????????push(stack,?p-1);?
????????push(stack,?l);
????}

????if?(p+1?//右半部分兩個邊界值入棧
????????push(stack,?u);
????????push(stack,?p+1);
????}

????while?(!IS_EMPTY(stack))?{?//棧不為空，則循環(huán)劃分過程
????????l?=?pop(stack);
????????u?=?pop(stack);
????????p?=?partition(a,?l,?u);

????????if?(p-1?>?l)?{
????????????push(stack,?p-1);
????????????push(stack,?l);
????????}

????????if?(p+1?????????????push(stack,?u);
????????????push(stack,?p+1);
????????}
????}
}

推薦閱讀：

【45期】盤點那些必問的數(shù)據(jù)結(jié)構(gòu)算法題之基礎(chǔ)排序

【44期】盤點那些必問的數(shù)據(jù)結(jié)構(gòu)算法題之二分查找算法

【43期】盤點那些必問的數(shù)據(jù)結(jié)構(gòu)算法題之二叉樹基礎(chǔ)

5T技術(shù)資源大放送！包括但不限于：C/C++，Linux，Python，Java，PHP，人工智能，單片機，樹莓派，等等。在公眾號內(nèi)回復(fù)「2048」，即可免費獲取！！

微信掃描二維碼，關(guān)注我的公眾號

朕已閱?