演算法——分治和快速排序

分治也是一種遞歸式問題解決方法。快速排序是使用分治法的一種排序演算法。

分治

分治一般有兩個步驟：找出基線條件，不斷將問題分解，直到符合基線條件。

例子：比如計算數組[2,4,6]中所有元素的和，可以使用循環，也可以使用分治遞歸。

接受一個列表，如果列表為空，就返回0.

否則，計算列表中除第一個數字外的其他數字的綜合，將其與第一個數字相加，再返回結果。

設計數組的遞歸函數，基線條件通常是數組為空或只包含一個元素。

快速排序

快速排序的原理：

首先從數組中選擇一個元素，這個元素被稱為基準值。

接下來找出比基準值小的元素以及比基準值大的元素，這被稱為分區。

得到了一個由所有小於基準值的數字組成的子數組，一個由所有大於基準值的數字組成的子數組，以及基準值。

再對子數組進行同樣的分組排序的操作，最後組合起來就是有序的數組。

下面是快速排序的代碼：

關於複雜度

實際上函數O(n)表示運行時間是c*n，c是演算法所需的固定時間量。

比如對於簡單查找和二分查找來說，簡單查找的運行時間是 ，而二分查找的運行時間是 。

雖然看起來是簡單查找的時間常量小，單數如果n非常大的情況下，二分查找的速度幾乎沒有變化，比簡單查找快得多。

每個演算法的複雜度都有個平均情況和最糟情況。比如針對快速排序，基準值的選擇對複雜度的影響就很大。

如果基準值選擇一直選擇第一個的話，調用棧非常長，但是如果每次都選擇中間那個的話，調用棧可以很短。

在最糟情況下，棧長為O(n)，而在最佳情況下，棧長為O(log n)。而每一層所需時間為O(n)。

在最佳情況下，整個演算法需要的時間為O(n) * O(log n) = O(n log n)。在最糟情況下，該演算法的運行時間為O(n) * O(n) = O(n2)。

小結

分治將問題逐步分解。使用分治處理列表時，基線條件很可能是空數組或只包含一個元 素的數組。

實現快速排序時，請隨機地選擇用作基準值的元素。快速排序的平均運行時間為O(n log n)。

大O表示法中的常量有時候事關重大，這就是快速排序比合併排序快的原因所在。

比較簡單查找和二分查找時，常量幾乎無關緊要，因為列表很長時，O(log n)的速度比O(n) 快得多。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！