資訊專欄INFORMATION COLUMN
摘要：再談大表示法快速排序的獨(dú)特之處在于其速度取決于選擇的基準(zhǔn)值。在平均情況下快速排序的運(yùn)行時(shí)間為在最糟情況下退化為?？焖倥判蚝秃喜⑴判虻乃惴ㄋ俣确謩e表示為和，是算法所需的固定時(shí)間量被稱為常量。
分而治之
分而治之(divide and conquer,D&C)是一種著名的遞歸式問題解決方法。
只能解決一種問題的算法畢竟用處有限,而D&C提供了解決問題的思路,是另一個(gè)可供你使用的工具。
D&C算法是遞歸的。使用D&C解決問題的過程包括兩個(gè)步驟。
(1) 找出基線條件,這種條件必須盡可能簡(jiǎn)單。
(2) 不斷將問題分解(或者說縮小規(guī)模),直到符合基線條件。
假設(shè)你是農(nóng)場(chǎng)主,有一小塊土地。如何將一塊地均勻地分成方塊,并確保分出的方塊是最大的呢?基線條件
最容易處理的情況是,一條邊的長(zhǎng)度是另一條邊的整數(shù)倍。比如，25m x 50m的土地可以分成 2 個(gè) 25m x 25m 的方塊。
遞歸條件根據(jù)D&C的定義,每次遞歸調(diào)用都必須縮小問題的規(guī)模。首先找出這塊地可容納的最大方塊。如，上圖可以劃出兩個(gè)640 m × 640 m的方塊,同時(shí)余下一小塊400m x 640m 地。
我們下一步要做的就是對(duì)余下的那一小塊地使用相同的算法。因?yàn)?strong>適用于這小塊地的最大方塊,也是適用于整塊地的最大方塊。換言之,你將均勻劃分1680 m × 640 m土地的問題,簡(jiǎn)化成了均勻劃分400m x 640 m土地的問題!
我們很容易實(shí)現(xiàn)上述過程。我們進(jìn)一步抽象，這個(gè)過程實(shí)際上就是求兩個(gè)整數(shù)的最大公倍數(shù)。
例2給定一個(gè)數(shù)字?jǐn)?shù)組，如，[2,4,6]，怎么返回這些數(shù)字相加后的結(jié)果。使用循環(huán)可以很容易實(shí)現(xiàn)。那使用遞歸怎么實(shí)現(xiàn)呢？基線條件
最簡(jiǎn)單的數(shù)組不包含任何元素或只包含一個(gè)元素,這個(gè)可以認(rèn)為是數(shù)組的基線條件。
遞歸條件每次遞歸調(diào)用都必須離空數(shù)組更近一步。我們通過下面的等式縮小問題的規(guī)模。
sum [2,4,6] == 2 + sum [4,6]
使用Haskell可以很容易實(shí)現(xiàn)：
sum [] = 0 sum (x:xs) = x + (sum xs)快速排序
快速排序是一種常用的排序算法,如，C語(yǔ)言標(biāo)準(zhǔn)庫(kù)中的函數(shù)qsort實(shí)現(xiàn)的就是快速排序。
基線條件數(shù)組為空或只包含一個(gè)元素。在這種情況下,只需原樣返回?cái)?shù)組。
遞歸條件我們從數(shù)組中選擇一個(gè)元素作為基準(zhǔn)值（pivot），然后以該值為基準(zhǔn)對(duì)數(shù)據(jù)分區(qū)（partitioning），這樣數(shù)組劃分成了三部分：
一個(gè)由所有小于基準(zhǔn)值的數(shù)字組成的子數(shù)組;
基準(zhǔn)值
一個(gè)由所有大于基準(zhǔn)值的數(shù)組組成的子數(shù)組。
這樣問題縮小到了子數(shù)組規(guī)模。再分別對(duì)子數(shù)組應(yīng)用以上過程，得到排序后的子數(shù)組，最終我們只要將這三部分拼接起來就能得到完全排序的數(shù)組。
注意：為了實(shí)現(xiàn)簡(jiǎn)單，基準(zhǔn)值每次都取的數(shù)組首元素。
代碼如下：
# 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
注意：上面的版本每次都新生成子數(shù)組，有些人認(rèn)為正確的快速排序應(yīng)該使用in-place交換，所以上面的算法不“正宗”。
再談大 O 表示法快速排序的獨(dú)特之處在于,其速度取決于選擇的基準(zhǔn)值。在平均情況下,快速排序的運(yùn)行時(shí)間為O(nlog n),在最糟情況下,退化為O(n2)。還有一種合并排序(merge sort)的排序算法，其運(yùn)行時(shí)間為O(nlogn)。
大O表示法體現(xiàn)出的是對(duì)元素規(guī)模n的增速，但處理每個(gè)元素的速度是有差異的，比如，對(duì)每個(gè)元素執(zhí)行(*2)和(+3).(*2)操作，明顯是后者執(zhí)行的時(shí)間長(zhǎng)。
快速排序和合并排序的算法速度分別表示為c1 nlogn和c2 nlogn，c是算法所需的固定時(shí)間量,被稱為常量。通常不考慮這個(gè)常量,因?yàn)槿绻麅煞N算法的大O運(yùn)行時(shí)間不同,這種常量將無關(guān)緊要。但有時(shí)候,常量的影響可能很大,對(duì)快速查找和合并查找來說就是如此。快速查找的常量比合并查找小,因此如果它們的運(yùn)行時(shí)間都為O(n log n),快速查找的速度將更快。實(shí)際上,快速查找的速度確實(shí)更快,因?yàn)橄鄬?duì)于遇上最糟情況,它遇上平均情況的可能性要大得多。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/43490.html
摘要：在本書中你將學(xué)習(xí)比較不同算法的優(yōu)缺點(diǎn)該使用合并排序算法還是快速排序算法或者該使用數(shù)組還是鏈表。這樣的算法包括快速排序一種速度較快的排序算法。 在讀《算法圖解》這本書，這本書有兩個(gè)優(yōu)點(diǎn)： 手繪風(fēng)格的圖，看著很讓人入戲； 算法采用Python語(yǔ)言描述，能更好的表達(dá)算法思想。 關(guān)于算法的學(xué)習(xí)有兩點(diǎn)心得： 算法思想最重要，理解了思想，算法是很容易寫出來的，所以盡量不要把過多精力放在細(xì)節(jié)上...
摘要：選擇排序是下一章將介紹的快速排序的基石。需要存儲(chǔ)多項(xiàng)數(shù)據(jù)時(shí)有兩種基本方式數(shù)組和鏈表。但它們并非都適用于所有的情形因此知道它們的差別很重要。選擇排序是一種靈巧的算法但其速度不是很快。 選擇排序是下一章將介紹的快速排序的基石。 內(nèi)存的工作原理 計(jì)算機(jī)就像是很多抽屜的集合體,每個(gè)抽屜都有地址。showImg(https://segmentfault.com/img/bVbpWvv?w=413...
摘要：概述快速排序最初由東尼霍爾提出，是一種平均時(shí)間復(fù)雜度為，最差時(shí)間復(fù)雜度為的排序算法。測(cè)試算法效率與復(fù)雜度完全隨機(jī)序列排序結(jié)果以下面的方法分別生成元素個(gè)數(shù)為萬萬的完全隨機(jī)數(shù)組，并用快速排序算法對(duì)其排序。 概述 快速排序（QuickSort）最初由東尼·霍爾提出，是一種平均時(shí)間復(fù)雜度為showImg(https://segmentfault.com/img/bV5sdO?w=61&h=17...
摘要：將大的先放在后面，再下一次可以把相同大的放在上一次的之前，順序改變。 之前介紹的排序算法： 【算法】插入排序——希爾排序+直接插入排序_Rinne’s blog-C...
閱讀 1141·2021-11-16 11:45
閱讀 3152·2021-10-13 09:40
閱讀 747·2019-08-26 13:45
閱讀 1245·2019-08-26 13:32
閱讀 2198·2019-08-26 13:23
閱讀 943·2019-08-26 12:16
閱讀 2847·2019-08-26 11:37
閱讀 1781·2019-08-26 10:32
