在快速排序之前，有一個(gè) D&C 的概念攘烛， 即 divede and conquer（分而治之）舔痕。具體什么意思呢评抚，就是說可以把一個(gè)問題不斷劃分成小問題，如果劃分到最后的小問題很容易解決伯复，那么劃分出來的問題都可以這樣做慨代，從而這個(gè)問題也解決了。
現(xiàn)在的問題是啸如，對(duì)一個(gè)數(shù)組進(jìn)行排序侍匙，可以先想一下，什么情況下數(shù)組不用排序叮雳，要么這個(gè)數(shù)組是一個(gè)空數(shù)組想暗，要么這個(gè)數(shù)組只有一個(gè)數(shù)字妇汗。那什么情況下數(shù)組排序最簡(jiǎn)單呢，就是數(shù)組只含有兩個(gè)數(shù)字说莫，只需要對(duì)這兩個(gè)數(shù)字比較大小杨箭，然后進(jìn)行位置變換就可以了。那么現(xiàn)在小問題的解決方案已經(jīng)有了唬滑，現(xiàn)在要做的就是把不是一下子可以解決的大問題劃分成一下子就可以解決的小問題告唆。
在快速排序時(shí)，按照這個(gè)思路晶密，可以先找一個(gè)基準(zhǔn)值擒悬，數(shù)組中比這個(gè)基準(zhǔn)值小的就放在它的左邊，否則放在右邊稻艰。這樣最開始的一個(gè)數(shù)組就變成了一個(gè)基準(zhǔn)值加上比它小的子數(shù)組和比它大的子數(shù)組懂牧，接下來可以對(duì)這兩個(gè)子數(shù)組按照這個(gè)方式繼續(xù)進(jìn)行劃分（遞歸條件），直到最后子數(shù)組中只有一個(gè)數(shù)字為止（基線條件）尊勿。
def quick_sort(array):
if len(array) < 2:
return array
else:
base_value = array[0] # 這里選擇第一個(gè)值作為基準(zhǔn)值
less = [v for v in array[1:] if v <= base_value]
greater = [v for v in array[1:] if v > base_value]
return quick_sort(less) + [base_value] + quick_sort(greater)
print(quick_sort([1, 3, 6, 2, 5, 4]))
>>>
[1, 2, 3, 4, 5, 6]
這里每次選擇基準(zhǔn)值時(shí)都是把第一個(gè)值作為基準(zhǔn)值僧凤，這樣有一個(gè)壞處就是，如果這個(gè)數(shù)組是升序的元扔，那么遞歸層次最深躯保，效率也最低。這時(shí)候算法的運(yùn)行時(shí)間為 O(n2)澎语。而最好的情況是每次選擇的值都在中間途事，兩邊的子數(shù)組等長(zhǎng)，這樣遞歸層次最淺擅羞，算法的運(yùn)行時(shí)間為 O(nlogn)尸变。在使用時(shí)，為了使平均運(yùn)行時(shí)間等同于最佳算法時(shí)間减俏，可以使用的方法是每次隨機(jī)取基準(zhǔn)值召烂。
