目錄

1）?示例1：

2）快速排序

3) 再談大O表示法

4）小結(jié)

---

本章內(nèi)容：學(xué)習(xí)分而治之，快速排序

1）?示例1：

假設(shè)你是農(nóng)場主，有一小塊土地，你要將這塊地均勻分成方塊，且分出的方塊盡可能大。如何分？

你要將這塊地均勻分成方塊，且分出的方塊要盡可能大。顯然，下面的分法不符合要求。

此時，你應(yīng)該使用D&C策略（divide and conquer）。包括兩步驟:

(1) 找出基線條件，這種條件必須盡可能簡單。

(2)不斷將問題分解（或者說縮小規(guī)模），直到符合基線條件。

下面就來使用D&C找出問題的解決方案。首先，找出基線條件。最容易處理的情況是，一條邊的長度是另一邊的整數(shù)倍。

現(xiàn)在找出遞歸條件，這正是D&C的用武之地。每次遞歸都必須縮小問題的規(guī)模，如何縮小問題的規(guī)模呢，首先，找出這塊地可容納的最大方塊。

如圖，劃出了兩個方塊，同時余下一小塊地。現(xiàn)在是頓悟時刻，何不對余下的那一小塊地使用相同的算法呢？

這里有一個關(guān)鍵的地方，就是適用于這小快地的最大方塊，也是適用于整塊地的最大方案。感興趣的可以查查歐幾里得算法。

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm

接下來就是使用同樣算法。直到余下土地為方塊。

? ? ? ? ? ?

? ? ??

現(xiàn)在我們找到了最大方塊，如下圖：

2）快速排序

快速排序是一種常用的排序算法，比選擇排序快得多，例如，C語言標(biāo)準(zhǔn)庫的函數(shù)qsort實(shí)現(xiàn)的就是快速排序。

對排序算法來說，最簡單的數(shù)組什么樣呢？就是根本不需要排序的數(shù)據(jù)。

因此，基線條件為數(shù)組為空或只包含一個元素。在這種情況，只需返回數(shù)組：

def quicksort(array):if len(array) < 2:return array

我們來看更長的數(shù)組。對包含兩個元素的數(shù)組進(jìn)行排序也很容易：

包含三個元素呢？

現(xiàn)在介紹快速排序的工作原理：首先，從數(shù)組中選擇一個元素，這個元素被稱為基準(zhǔn)值(pivot).

我們暫時將數(shù)組的第一個元素用作基準(zhǔn)值.接下來，找出比基準(zhǔn)值小的元素以及比基準(zhǔn)值大的元素。

這被稱為分區(qū)(partitioning)。這里只進(jìn)行了分區(qū)，得到的兩個子數(shù)組是無序的。如何對子數(shù)組進(jìn)行排序呢？對于包含兩個元素的數(shù)組以及空數(shù)組，快速排序知道如何將它們排序。因此對這兩個子數(shù)組進(jìn)行快速排序，再合并結(jié)果，就得到一個有序數(shù)組！

quicksort([15, 10]) + [33] + quicksort([]) > [10, 15, 33]

現(xiàn)在我們知道了如何對包含三個元素的數(shù)組進(jìn)行排序了：

（1）選準(zhǔn)基準(zhǔn)值。

（2）將數(shù)組分成兩個子數(shù)組：小于基準(zhǔn)值的元素和大于基準(zhǔn)值的元素。

（3）對這兩個子數(shù)組進(jìn)行快速排序。

下面是快速排序的代碼：

def quicksort(array):if len(array) < 2:return arrayelse:pivot = array[0]less = [i for i in array if i<= pivot]greater = [i for in array if i > pivot]return quicksort(less) + [pivot] + quicksort(greater)

?

3) 再談大O表示法

我們再來看看常見的大O運(yùn)行時間：

這里需要說明的是，在平均情況下，快速排序的運(yùn)行時間為O(n logn)。

快速排序的性能高度依賴于你選擇的基準(zhǔn)值。來看下面這樣一個有序數(shù)組，每次都選擇第一個元素為基準(zhǔn)值，來看看快速排序過程，

現(xiàn)在選擇中間元素作為基準(zhǔn)值，看看排序過程：

第一個示例展示的是最糟情況，棧長為O(n)，第二個示例展示的是最佳情況，棧長為O(log n)。與此同時，在調(diào)用棧的每層都涉及全部8個元素，操作數(shù)為O(n)。

現(xiàn)在可以得出快速排序的運(yùn)行時間為O(n logn)（最佳情況），最佳情況也是平均情況。

4）小結(jié)

• D&C將問題逐步分解，使用D&C處理列表時，基線條件很可能是空數(shù)組或只包含一個元素的數(shù)組；
• 實(shí)現(xiàn)快速排序時，請隨機(jī)選地選擇用做基準(zhǔn)值的元素，快速排序的平均運(yùn)行時間為O(n log n);
• 大O表示法中的常量有時候事關(guān)重大，這就是快速排序比合并排序快的原因所在；
• 比較簡單查找和二分查找時，常量幾乎無關(guān)緊要，因為列表很長時，O(log n)的速度為O(n)塊很多。

總結(jié)

以上是生活随笔為你收集整理的图解算法学习笔记（四）：快速排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。