【算法】算法圖解筆記_快速排序

YanceyOfficial 發布于2019-07-31 10:14 / 782人閱讀

摘要：再談大表示法快速排序的獨特之處在于其速度取決于選擇的基準值。在平均情況下快速排序的運行時間為在最糟情況下退化為。快速排序和合并排序的算法速度分別表示為和，是算法所需的固定時間量被稱為常量。

分而治之

分而治之(divide and conquer,D&C)是一種著名的遞歸式問題解決方法。
只能解決一種問題的算法畢竟用處有限,而D&C提供了解決問題的思路,是另一個可供你使用的工具。

D&C算法是遞歸的。使用D&C解決問題的過程包括兩個步驟。
(1) 找出基線條件,這種條件必須盡可能簡單。
(2) 不斷將問題分解(或者說縮小規模),直到符合基線條件。

例1

假設你是農場主,有一小塊土地。如何將一塊地均勻地分成方塊,并確保分出的方塊是最大的呢?

基線條件

最容易處理的情況是,一條邊的長度是另一條邊的整數倍。比如，25m x 50m的土地可以分成 2 個 25m x 25m 的方塊。

遞歸條件

根據D&C的定義,每次遞歸調用都必須縮小問題的規模。首先找出這塊地可容納的最大方塊。如，上圖可以劃出兩個640 m × 640 m的方塊,同時余下一小塊400m x 640m 地。
我們下一步要做的就是對余下的那一小塊地使用相同的算法。因為適用于這小塊地的最大方塊,也是適用于整塊地的最大方塊。換言之,你將均勻劃分1680 m × 640 m土地的問題,簡化成了均勻劃分400m x 640 m土地的問題!

我們很容易實現上述過程。我們進一步抽象，這個過程實際上就是求兩個整數的最大公倍數。

例2

給定一個數字數組，如，[2,4,6]，怎么返回這些數字相加后的結果。使用循環可以很容易實現。那使用遞歸怎么實現呢？

基線條件

最簡單的數組不包含任何元素或只包含一個元素,這個可以認為是數組的基線條件。

遞歸條件

每次遞歸調用都必須離空數組更近一步。我們通過下面的等式縮小問題的規模。
sum [2,4,6] == 2 + sum [4,6]

使用Haskell可以很容易實現：

sum [] = 0
sum (x:xs) = x + (sum xs)

快速排序

快速排序是一種常用的排序算法,如，C語言標準庫中的函數qsort實現的就是快速排序。

基線條件

數組為空或只包含一個元素。在這種情況下,只需原樣返回數組。

遞歸條件

我們從數組中選擇一個元素作為基準值（pivot），然后以該值為基準對數據分區（partitioning），這樣數組劃分成了三部分：

一個由所有小于基準值的數字組成的子數組;

基準值

一個由所有大于基準值的數組組成的子數組。

這樣問題縮小到了子數組規模。再分別對子數組應用以上過程，得到排序后的子數組，最終我們只要將這三部分拼接起來就能得到完全排序的數組。

注意：為了實現簡單，基準值每次都取的數組首元素。

代碼如下：

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

--haskell
import Data.List

quickSort :: Ord a => [a] -> [a]
quickSort [] = []
quickSort (x:xs) = quickSort lhs ++ [x] ++ quickSort rhs
  where
    (lhs, rhs) = partition (< x) xs

注意：上面的版本每次都新生成子數組，有些人認為正確的快速排序應該使用in-place交換，所以上面的算法不“正宗”。

再談大 O 表示法

快速排序的獨特之處在于,其速度取決于選擇的基準值。在平均情況下,快速排序的運行時間為O(nlog n),在最糟情況下,退化為O(n2)。還有一種合并排序(merge sort)的排序算法，其運行時間為O(nlogn)。

大O表示法體現出的是對元素規模n的增速，但處理每個元素的速度是有差異的，比如，對每個元素執行(*2)和(+3).(*2)操作，明顯是后者執行的時間長。
快速排序和合并排序的算法速度分別表示為c1 nlogn和c2 nlogn，c是算法所需的固定時間量,被稱為常量。通常不考慮這個常量,因為如果兩種算法的大O運行時間不同,這種常量將無關緊要。但有時候,常量的影響可能很大,對快速查找和合并查找來說就是如此。快速查找的常量比合并查找小,因此如果它們的運行時間都為O(n log n),快速查找的速度將更快。實際上,快速查找的速度確實更快,因為相對于遇上最糟情況,它遇上平均情況的可能性要大得多。

云服務器 GPU云服務器排序算法圖解快速排序算法最好的快速排序算法最快速的排序算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/43490.html

【算法】算法圖解筆記_算法簡介

摘要：在本書中你將學習比較不同算法的優缺點該使用合并排序算法還是快速排序算法或者該使用數組還是鏈表。這樣的算法包括快速排序一種速度較快的排序算法。在讀《算法圖解》這本書，這本書有兩個優點：手繪風格的圖，看著很讓人入戲；算法采用Python語言描述，能更好的表達算法思想。關于算法的學習有兩點心得：算法思想最重要，理解了思想，算法是很容易寫出來的，所以盡量不要把過多精力放在細節上...

tomlingtm 2019-07-31 10:10 評論0 收藏0
【算法】算法圖解筆記_選擇排序

摘要：選擇排序是下一章將介紹的快速排序的基石。需要存儲多項數據時有兩種基本方式數組和鏈表。但它們并非都適用于所有的情形因此知道它們的差別很重要。選擇排序是一種靈巧的算法但其速度不是很快。選擇排序是下一章將介紹的快速排序的基石。內存的工作原理計算機就像是很多抽屜的集合體,每個抽屜都有地址。showImg(https://segmentfault.com/img/bVbpWvv?w=413...

mylxsw 2019-07-31 10:12 評論0 收藏0
快速排序算法圖解與PHP實現講解

摘要：概述快速排序最初由東尼霍爾提出，是一種平均時間復雜度為，最差時間復雜度為的排序算法。測試算法效率與復雜度完全隨機序列排序結果以下面的方法分別生成元素個數為萬萬的完全隨機數組，并用快速排序算法對其排序。概述快速排序（QuickSort）最初由東尼·霍爾提出，是一種平均時間復雜度為showImg(https://segmentfault.com/img/bV5sdO?w=61&h=17...

shleyZ 2019-06-28 18:31 評論0 收藏0
【算法】計數排序 + 各個排序算法的穩定性

摘要：將大的先放在后面，再下一次可以把相同大的放在上一次的之前，順序改變。之前介紹的排序算法：【算法】插入排序——希爾排序+直接插入排序_Rinne’s blog-C...

不知名網友 2021-11-29 10:50 評論0 收藏0