快速排序是一種常用的優(yōu)雅的排序算法，它使用分而治之的策略。
那么分而治之（D&C）是一種怎樣的策略呢？
分而治之
分而治之（D&C）的要點(diǎn)只有兩個(gè)：
找出簡單的基線問題
確定如何縮小問題的規(guī)模，使其符合基線條件
D&C不是一種解決問題的算法，而是一種解決問題的思路。比如看下面這個(gè)例子：
這是一個(gè)數(shù)字?jǐn)?shù)組：
你需要將這些數(shù)字相加，并返回結(jié)果。使用循環(huán)可以很輕松地解決這個(gè)問題：
def sum(arr):
"""一個(gè)數(shù)組元素相加的循環(huán)"""
total = 0
for i in arr:
total += i
return total
print(sum([2, 4, 6]))
但是如何使用遞歸函數(shù)來完成這種任務(wù)呢？
- 第一步：找出基線條件。如何一個(gè)數(shù)組只包含一個(gè)或者零個(gè)元素，那計(jì)算總和將會(huì)非常容易：
這就是基線條件
- 第二步：縮小問題規(guī)模，使其符合基線條件。如果遞歸調(diào)用都使其里空數(shù)組更近了一步，那么這就縮小了問題規(guī)模。
下面用代碼實(shí)現(xiàn)這個(gè)過程：
def sum(arr):
"""計(jì)算列表的各元素總和"""
if arr == []:
return 0
else:
return arr[0] + sum(arr[1:])
s = sum([2, 4, 6])
print(s)
說了這么多，卻好像還是在說遞歸的知識(shí)，這和快速排序有什么關(guān)系呢？
快速排序
對于排序算法來說，最簡單的數(shù)組是什么樣的？對，沒錯(cuò)，最簡單的數(shù)組就是不需要排序的數(shù)組：
因此，在涉及多個(gè)元素的數(shù)組進(jìn)行排序的時(shí)候，我們可以利用分而治之策略：將數(shù)組分解，直到滿足基線條件為止。
簡要敘述一下快速排序的基本思想：
首先，從數(shù)組中選取一個(gè)元素，這個(gè)元素被稱為基準(zhǔn)值
將數(shù)組分為兩個(gè)子數(shù)組：小于基準(zhǔn)值的元素和大于基準(zhǔn)值的元素
對這兩個(gè)子數(shù)組進(jìn)行快速排序
可能有小伙伴到這里又懵了，這不還是沒有說清楚快速排序到底是怎么排的嘛。
客官別急，下面來說快速排序的具體實(shí)現(xiàn)步驟：
設(shè)置兩個(gè)變量i、j，排序開始的時(shí)候：i=0，j=N-1
以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A[0]
從j開始向前搜索，即由后開始向前搜索(j--)，找到第一個(gè)小于key的值A(chǔ)[j]，將A[j]和A[i]互換
從i開始向后搜索，即由前開始向后搜索(i++)，找到第一個(gè)大于key的A[i]，將A[i]和A[j]互換
重復(fù)第3、4步，直到i=j
用一個(gè)例子來說明：
下面用代碼實(shí)現(xiàn)快速排序：
def quicksort(array):
"""快速排序"""
if len(array) < 2:
return array # 基線條件：為空或者只包含一個(gè)元素的數(shù)組是有序的
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)值的元素組成的子數(shù)組
return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([10, 5, 2, 3]))
再談大O表示法
快速排序的獨(dú)特之處在于，其速度取決于選擇的基準(zhǔn)值。這也就產(chǎn)生了最佳情況和最糟情況之分。
在最佳情況下，快速排序的運(yùn)行時(shí)間為O(n ㏒n)。
在最糟情況下，快速排序的運(yùn)行時(shí)間為O(n2)。
說明：最佳情況也是平均情況。
我們一般使用大O表示法都是指的算法的平均情況，所以我們一般認(rèn)為快速排序的運(yùn)行時(shí)間為O(n ㏒n)。至于何為最佳情況和最糟情況，這里不再過多闡述了。
小結(jié)
大O表示法指的是算法的平均時(shí)間
大O表示法省略了常數(shù)
快速排序的平均運(yùn)行時(shí)間為O(n ㏒n)
使用D&C處理列表時(shí)，基線條件一般是空數(shù)組或只包含一個(gè)元素的數(shù)組
每天學(xué)習(xí)一點(diǎn)點(diǎn)，每天進(jìn)步一點(diǎn)點(diǎn)。
