dw做單頁網(wǎng)站教程seo排名點(diǎn)擊軟件運(yùn)營
文章目錄
- 1. 不穩(wěn)定 + 就地
- 2. 最好情況 + 最壞情況
- 3.平均情況
1. 不穩(wěn)定 + 就地
以下針對(duì)剛才所給出的快速排序算法的第一個(gè)版本，就其性能做一分析。
首先很遺憾地發(fā)現(xiàn)，這個(gè)算法是不穩(wěn)定的。快速排序算法的不穩(wěn)定性通過我們剛才所舉的那個(gè)實(shí)例可以清楚地看出來。
注意到，在原始的輸入序列中有兩個(gè)5，按照先后次序，我們分別用5A 和5B 來表示。
在經(jīng)過一次劃分之后，我們可以看到這兩個(gè)元素的位置已經(jīng)彼此顛倒。實(shí)際上這種現(xiàn)象必然是普遍存在的。因?yàn)閷?duì)于任何兩個(gè)小于候選軸點(diǎn)的元素而言，它們加入子序列 L 的次序必然是顛倒的。同理對(duì)于大于候選軸點(diǎn)的雷同元素而言，也有對(duì)稱的性質(zhì)。
其次整個(gè)算法也是可以就地實(shí)現(xiàn)的，也就是說它只需要常數(shù)的附加空間。這一點(diǎn)從剛才這組原理和過程圖中也可以清晰地看出。
實(shí)際上除了原始的輸入序列，我們這里只需要維護(hù)常數(shù)個(gè)指針以及用于保存候選軸點(diǎn)的一個(gè)單元。
2. 最好情況 + 最壞情況
那么整個(gè)算法的運(yùn)行時(shí)間呢？我們知道，對(duì)于歸并排序而言，整個(gè)算法的運(yùn)行時(shí)間可以保證不超過 n*log n。我們也知道其關(guān)鍵在于歸并排序可以保證任何一對(duì)被劃分出來的子任務(wù)在規(guī)模上都是彼此相當(dāng)?shù)?#xff0c;也就是規(guī)模都接近二分之N。因此總體的運(yùn)行時(shí)間也就是求解兩個(gè)這樣的問題，再加上為了將它們的結(jié)果合并所需要的線性時(shí)間。
很遺憾，快速排序算法卻不能像歸并排序算法那樣保證子任務(wù)劃分時(shí)的均衡性。實(shí)際上partition 算法的每次劃分結(jié)果與其說是取決于這個(gè)算法，不如說取決于最初選定的候選軸點(diǎn)。
如果候選軸點(diǎn)在最終有序列中所對(duì)應(yīng)的秩為 r，那么經(jīng)劃分之后所得到的序列 L 的長度也必然就是 r。而對(duì)應(yīng)的子序列 G 的長度也必然為 n 減 1 再減 r。劃分的結(jié)果是否均衡完全取決于我們的運(yùn)氣。
-
在最好的情況下，我們的每次劃分都是均衡的，或者至少是接近均衡的，于是我們自然可以達(dá)到最優(yōu)的 n*logn。
-
然而反過來，在最壞的情況下，有可能我們的每一次劃分都不均衡，甚至極不均衡。比如最為極端的一種情況就是，每一個(gè)候選節(jié)點(diǎn)都是在當(dāng)前而言最小或者最大的極值元素，以至于在劃分之后，子序列 L 為空或者 G 為空。也就是說，在我們所劃分出來的一對(duì)子任務(wù)中，總是有一個(gè)規(guī)模為零，而另一個(gè)相對(duì)于此前的規(guī)模只減少了一個(gè)單位。
根據(jù)這個(gè)遞推式不難解出，此時(shí)算法所需要的總體運(yùn)行時(shí)間必然是平方量級(jí)的。也就說與起泡排序等低級(jí)算法居然性能是相當(dāng)?shù)摹?/strong>
當(dāng)然采用一些簡明的策略，在付出足夠小的代價(jià)之后，我們的確可以在一定程度上降低最壞情況出現(xiàn)的概率。比如我們可以采用所謂隨機(jī)選取法，也就說不再是每次都固定地將首元素作為候選軸點(diǎn)。而是在整個(gè)序列中，隨機(jī)地選擇其一。另一種更為有效的方法是所謂的三者取中法，也就是說我們每次都是在整個(gè)序列中隨機(jī)地抽取3個(gè)元素，然后將其中數(shù)值居中的那個(gè)作為候選軸點(diǎn)。
當(dāng)然，無論采用什么方法，我們也只能是在一定程度上降低最壞情況出現(xiàn)的概率，而無法根本的杜絕最壞情況的出現(xiàn)。既然如此，我們接下來不得不回答的一個(gè)問題就是，就基本的快速排序算法而言，其平均性能又有多高呢？
3.平均情況
非常幸運(yùn)的是，以上基本的快速排序算法在常規(guī)的隨機(jī)意義下，平均性能的確可以達(dá)到最優(yōu)的 n log n。
以下我們不妨針對(duì)最為常見的均勻獨(dú)立分布來做一精確的估算，也就說我們?cè)谶@里假設(shè)，所有的元素都是均勻的取自于某一個(gè)數(shù)值范圍。同時(shí)各元素在確定各自取值時(shí)是互不依賴的。
我們來考察任何一個(gè)這樣的隨機(jī)序列，調(diào)用 partition 算法對(duì)它進(jìn)行的劃分將有幾種可能呢？無非 n 種可能，具體的哪種情況完全取決于最初所選定的那個(gè)候選軸點(diǎn)。
更準(zhǔn)確地講，是這個(gè)候選軸點(diǎn)在最終有序列中所具有的秩。如果將候選軸點(diǎn)的這個(gè)秩記作 k，那么 partition 算法所輸出的子序列 L 長度也應(yīng)該是 k，這個(gè)子序列所對(duì)應(yīng)的那個(gè)子任務(wù)所需的平均運(yùn)行時(shí)間也因此就可以表示為Tk。對(duì)稱的 partition 算法所輸出的子序列 G 長度應(yīng)該為 n 減 k 減1，這個(gè)子序列所對(duì)應(yīng)的那個(gè)子任務(wù)從遞歸的角度來看，所需要的平均運(yùn)行時(shí)間也因此可以表示為 T n 減 k 再減1。這樣的一對(duì)排序子任務(wù)總共所需要的運(yùn)行時(shí)間也自然就是二者之和。
進(jìn)一步的，既然按照假設(shè)這里服從均勻獨(dú)立分布，因此各種情況出現(xiàn)的概率應(yīng)該均等。具體來說都是 n 分之1。因此所有這些情況所對(duì)應(yīng)的平均運(yùn)行時(shí)間，也就是用這個(gè)概率對(duì)它們的總和進(jìn)行平均。以下的分析，焦點(diǎn)就會(huì)聚在這個(gè)求和號(hào)上。盡管這個(gè)求和涉及到前后兩個(gè)序列，但是略加觀察之后，我們不難發(fā)現(xiàn)，這兩個(gè)序列的求和應(yīng)該完全是相等的，你能看出原因來嗎？
沒錯(cuò)，這兩個(gè)序列的取值范圍都是從 0 到 n 減1 ，只不過前者是遞增的，從0到 n 減1，而后者只不過是遞減的，從 n 減1到0。因此我們只需保留其中的一項(xiàng)，同時(shí)作為補(bǔ)償將它的系數(shù)加倍。
接下來我們將這個(gè)等式的兩端同時(shí)乘以 n，于是就可以得到這樣一個(gè)等式。如果將其中所有的 n 都替換為 n 減1，我們又可以進(jìn)而得到下面這個(gè)等式?，F(xiàn)在我們只需將這兩個(gè)等式相減，就可以得到這樣一個(gè)等式。除了系數(shù)，這個(gè)等式主要都包含一個(gè) Tn 以及兩個(gè) T n 減一。
接下來我們只需對(duì) Tn 和 Tn 減1合并同類項(xiàng)，就可以得到這樣一個(gè)等式。對(duì)于這樣一個(gè)等式，我們不妨令它的左右兩端同時(shí)除以 n 以及 n 加1。
于是就可以得到這樣一個(gè)等式，如果我們將這個(gè)等式的左側(cè)表示和理解為另一個(gè)函數(shù) Sn，那么右側(cè)的這一項(xiàng)也就對(duì)應(yīng)于 Sn 減1。這樣我們也得到了一個(gè)關(guān)于 Sn 的簡明遞推式。
因此接下來，我們可以進(jìn)而將右側(cè)的 Sn 減 1 替換為 Sn 減2。當(dāng)然，為此我們需要追加一項(xiàng)，這種地推可以持續(xù)進(jìn)行下去，也就說我們可以將 Sn 減2替換為 Sn 減3，再將 Sn 減3替換為 Sn 減4以及 Sn 減4替換成 Sn 減5，諸如此類。
在遞推到最終一步之前，我們所引入的各項(xiàng)將構(gòu)成一個(gè)級(jí)數(shù)。你應(yīng)該看得出來這是一個(gè)什么級(jí)數(shù)。沒錯(cuò)，調(diào)和級(jí)數(shù)。我們?cè)诘谝徽戮驮榻B過，就漸進(jìn)意義而言，調(diào)和級(jí)數(shù)是與自然對(duì)數(shù) log n 同階的。
由此可見，我們這里所需要估計(jì)的快速排序算法的平均運(yùn)行時(shí)間在漸進(jìn)意義下的確不超過 n * log n，那么它對(duì)應(yīng)的常系數(shù)呢？為此，我們只需將 log n 替換為以2為底的對(duì)數(shù)，相應(yīng)的也自然可以得知常系數(shù)應(yīng)為兩倍的 ln2，具體來說也就大致為1.39。
這樣小的一個(gè)長系數(shù)，也保證了快速排序算法在通常情況下的優(yōu)異性能，也就是說，快速排序的確名符其實(shí)。