算法圖解 | 分而治之與快速排序算法
分而治之D&C
分而治之不是一種解決問題的算法，而是一種希望問題分解，將複雜的問題劃分為多個簡單問題來解決的思想。
分而治之的思想重點：
（1）找出簡單的基線條件
（2）確定如何縮小問題的規模，使其符合基線條件。
快速排序
例如快速排序問題，一個列表進行排序，如下圖
首先選擇列表中的一個元素作為基準元素，其他的元素都與這個元素做比較，找出小於這個基準值的值、大於基準值的值。這稱為“分區”，這時有，
1）一個由所有小於基準值的數字組成的子數組；
2）基準值
3）一個由所有大於基準值的數組組成的子數組
然後再將“小於v”和“大於v”的數據塊作為子數組，同樣選擇基準值，再進行上述類似操作，當執行到數據塊中只有1個元素或者0個元素時，即完成排序。
這個問題中的基線條件是執行到數據塊中只有1個或者0個元素；
例如下面的數組，進行排序：
根據選擇的基準值，對這個數組進行分區的各種可能方式如下：
假設你將3用作基準值，可對得到的子數組進行快速排序。
還有一個例子，如下圖：
圖片來自極客學院
快速排序代碼：
算法複雜度
看一下其他的算法的複雜度（O表示法表示）
快速排序的性能高度依賴於你選擇的基準值。
最糟情況：算法複雜度O(n^2)
假設總是將第一個元素用作基準值，且要處理的數組是有序的。由於快速排序算法不檢查輸入數組是否有序，因此它依然嘗試對其進行排序。
注意，數組並沒有被分成兩半，相反，其中一個子數組始終為空，這導致調用棧非常長。
這個示例展示的是最糟情況，在最糟情況下，棧長為O(n)，在調用棧的每層都涉及O(n)個元素，完成每層所需的時間都為O(n)。因此整個算法需要的時間為O(n) * O(n) = O(n^2)。
最佳情況：算法複雜度O(n log n)
假設總是將中間的元素用作基準值，在這種情況下，調用棧如下。
調用棧短得多！因為每次都將數組分成兩半，所以不需要那麼多遞歸調用。很快就到達
了基線條件，因此調用棧短得多。
這個示例展示的是最佳情況，在最佳情況下，棧長為O(log n)，每一層運行時間為O(n),所以整個算法需要的時間為O(n) * O(log n) = O(n log n)。
平均情況：算法複雜度O(n log n)
最佳情況也是平均情況。只要每次都隨機地選擇一個數組元素作為基準值，快速排序的平均運行時間就將為O(n log n)。快速排序是最快的排序算法之一，也是D&C典範。
如何選擇基準值?
實現快速排序時，請隨機地選擇用作基準值的元素。快速排序的平均運行時間為O(n log n)。
總結
1）D&C將問題逐步分解。使用D&C處理列表時，基線條件很可能是空數組或只包含一個元
素的數組。
2）實現快速排序時，請隨機地選擇用作基準值的元素。快速排序的平均運行時間為O(n log n)。
3）大O表示法中的常量有時候事關重大，這就是快速排序比合並排序快的原因所在。
更多細節參考《算法圖解》
私信發送“算法”獲取《算法圖解》PDF,發送“算法地圖”獲取機器學習算法地圖。
閱讀更多 AI深度學習求索 的文章
