以前也無(wú)數(shù)次的看過(guò)快速排序雄人，也無(wú)數(shù)次死記硬背過(guò)快排哟冬，今天再次看到快排的時(shí)候才恍然大悟嫂便，原來(lái)可以這么簡(jiǎn)單的實(shí)現(xiàn)快排捞镰。廢話不說(shuō)了，直接開車吧毙替。
快排是一種采用分而治之(divide and conquer,D&C)思想的算法岸售，D&C也是一種著名的遞歸式解決問(wèn)題的方法。既然是遞歸算法厂画，那么解決問(wèn)題的過(guò)程通常就包括了兩個(gè)步驟冰评。
- 找到盡可能簡(jiǎn)單的基線條件
- 不斷將問(wèn)題分解（或者縮小規(guī)模），直到符合基線條件
那么對(duì)于排序算法來(lái)說(shuō)木羹，最簡(jiǎn)單的數(shù)組時(shí)什么樣呢甲雅？
最簡(jiǎn)單的數(shù)組
因此，基線條件為數(shù)組為空或只包含一個(gè)元素坑填，這樣的情況下抛人，只需要原樣返回?cái)?shù)組——根本不用排序。
def quicksort(array):
if len(array)<2:
return array
對(duì)包含兩個(gè)元素的數(shù)組排序只需要比較大小交換順序就可以了
對(duì)兩個(gè)元素排序
對(duì)包含三個(gè)元素的數(shù)組呢脐瑰？不要忘了咱使用的可是D&C妖枚，根據(jù)遞歸策略，對(duì)數(shù)組進(jìn)行分解苍在，直到滿足基線條件绝页。接下來(lái)是快排的工作原理了：
首先從數(shù)組中選擇一個(gè)元素，一般被叫做基準(zhǔn)值（pivot）寂恬，一般我們會(huì)將數(shù)組的第一個(gè)元素作為基準(zhǔn)值（其實(shí)不一定合適）续誉，接下來(lái)找到比基準(zhǔn)值小和大的元素，即分區(qū)（partitioning）初肉。如下圖所示：
含有3個(gè)元素的數(shù)組
分區(qū)（partitioning）
現(xiàn)在我們有：
- 一個(gè)由小于基準(zhǔn)值的數(shù)字組成的子數(shù)組
- 基準(zhǔn)值
- 一個(gè)由大于基準(zhǔn)值數(shù)組組成的子數(shù)組
以上只是進(jìn)行了分區(qū)酷鸦，得到的兩個(gè)子數(shù)組是無(wú)序的，如果是有序的，那么合并后就是一個(gè)有序的數(shù)組了臼隔。那么如何對(duì)子數(shù)組進(jìn)行排序呢嘹裂？快排知道如何將他們排序，因此只需要進(jìn)行快排摔握，然后合并結(jié)果就可以了寄狼。
quicksort([15,10]) + [33] + quicksort([])
> [10,15,30]
因此最后實(shí)現(xiàn)快排的代碼：
def quickSort(array):
"""
快速排序
"""
if len(array) < 2:
return array # -----------基線條件
else:
pivot = array[0] # -----------遞歸條件
less = [i for i in array[1:] if i <= pivot] # -------由所有小于基準(zhǔn)值的元素組成的子數(shù)組
greater = [i for i in array[1:] if i > pivot] # -------由所有大于基準(zhǔn)值的元素組成的字?jǐn)?shù)組
return quickSort(less) + [pivot] + quickSort(greater)
print(quickSort([9, 4, 6, 10, 30, 26, 4]))
> [4, 4, 6, 9, 10, 26, 30]
說(shuō)好的3行代碼呢！借助于python的簡(jiǎn)潔氨淌，上面的代碼可以簡(jiǎn)化為：
def quicksort(array):
if len(array) < 2: return array
return quicksort([lt for lt in array[1:] if lt < array[0]]) + [array[0]] + quicksort([ge for ge in array[1:] if ge >= array[0]])
