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