4 快速排序
4.1 分而治之（divide and conquer簿寂，D&C）
一種解決問題的思路：將新問題遞歸到可解決已解決的問題上去尘盼√胳或者可稱為：歸納法猾昆。
使用 D&C 解決問題的過程包括兩個(gè)步驟：
找出基線條件觅够，這種條件必須盡可能簡單胶背。
不斷將問題分解（或者說縮小規(guī)模），直到符合基線條件喘先。
D&C 并非可用于解決問題的算法钳吟，而是一種解決問題的思路。
4.2 快速排序
使用D&C來解決窘拯，針對(duì)一個(gè)數(shù)組進(jìn)行快速排序红且。
step1
先確定最簡單的情況（即基線條件）—— 空數(shù)組，或只有1個(gè)元素的數(shù)組——這種數(shù)組不用排序涤姊！
#基線條件為數(shù)組為空或只包含一個(gè)元素暇番。在這種情況下，只需原樣返回?cái)?shù)組——根本就不用排序思喊。
def quicksort(array):
if len(array) < 2:
return array
step2
比基線情況復(fù)雜一點(diǎn)時(shí)：有兩個(gè)元素的數(shù)組——只需要比較這兩個(gè)元素的大小即可壁酬。
step3
三個(gè)元素的數(shù)組：D&C 的思路——將數(shù)組分解，直到滿足基線條件恨课。
快速排序的做法是：從數(shù)據(jù)中選出一個(gè)基準(zhǔn)值舆乔，然后找出比基準(zhǔn)值小的元素及比基準(zhǔn)值大的元素，相當(dāng)于構(gòu)造了一個(gè)分區(qū)剂公，形成了：
- 一個(gè)由所有小于基準(zhǔn)值的數(shù)字組成的子數(shù)組希俩；
- 基準(zhǔn)值；
- 一個(gè)由所有大于基準(zhǔn)值的數(shù)組組成的子數(shù)組纲辽。
接下來要做的事情就是使用step2來解決即可颜武，也就是贫母，有三個(gè)元素的數(shù)組快速排序步驟如下：
- 選擇基準(zhǔn)值。
- 將數(shù)組分成兩個(gè)子數(shù)組：小于基準(zhǔn)值的元素和大于基準(zhǔn)值的元素盒刚。
- 對(duì)這兩個(gè)子數(shù)組進(jìn)行快速排序。
依此類推绿贞，包含4個(gè)因块、5個(gè)，n個(gè)元素的情形也是如此籍铁。
快速排序代碼
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])
4.3 快速排序的速度
快速排序的性能高度依賴所選擇的基準(zhǔn)值涡上，如果選擇的基準(zhǔn)值合適，速度最佳情況可達(dá)到O(NlogN) ,每層比較N次拒名，層數(shù)由選擇的基礎(chǔ)值確定吩愧。
最糟情況則需要O(NN),這意味著每次選擇的基準(zhǔn)值都是最大或最小值。
只要每次隨機(jī)的選擇基準(zhǔn)值增显，快速排序的平均運(yùn)行時(shí)間即可達(dá)到最優(yōu)情況雁佳，即O(N*logN)。 快速排序是最快的排序算法之一同云。
5 散列表
散列表糖权，一種一一映身，以便快速查找——python中的字典竟然就是一種散列表炸站！
5.1 散列表的基本用途
先看用途星澳，再看散列表結(jié)構(gòu)。
- 模擬映射關(guān)系旱易；
- 防止重復(fù)禁偎；
- 緩存/記住數(shù)據(jù)，以免服務(wù)器再通過處理來生成它們阀坏。
5.2 散列表是什么樣的
直接解釋有點(diǎn)復(fù)雜如暖，用一個(gè)問題來描述：類似于超市中的產(chǎn)品條碼對(duì)應(yīng)到其價(jià)格——
- 如果用本子(無序)來記錄，在查找時(shí)通常需要O(N)時(shí)間全释；
- 如果是有序的装处，則可以用之前的二分法，大約O(logN)時(shí)間浸船；
但通常我們?nèi)バ〉昀镔I東西時(shí)妄迁，問老板，老板大都是立即告訴我們單價(jià)的李命，他在‘大腦’中形成了一種映射登淘，輸出一個(gè)物品名稱——對(duì)應(yīng)輸出一個(gè)價(jià)格。
我們希望在物品量更多時(shí)封字，仍能達(dá)到這一效果：即輸入物品黔州，立即獲得一個(gè)價(jià)格反饋——這就像一種映射函數(shù)耍鬓，在散列表中稱為散列函數(shù)。
散列函數(shù)是這樣的函數(shù)流妻，即無論你給它什么數(shù)據(jù)牲蜀，它都還你一個(gè)數(shù)字——散列函數(shù)“將輸入映射到數(shù)字”：滿足兩個(gè)條件，必需前后是一致的绅这，即相同的輸入得到相同的結(jié)果涣达；它必需將不同的輸入映身到不同的數(shù)字。
通過散列函數(shù)將一個(gè)數(shù)組和另一個(gè)數(shù)組對(duì)應(yīng)起來证薇，即構(gòu)成了一個(gè)散列表（hash table）.
如果不清楚度苔，看一看python的字典結(jié)構(gòu)即可：
book = dict()
book["apple"] = 0.67 ←------一個(gè)蘋果的價(jià)格為67美分
book["milk"] = 1.49 ←------牛奶的價(jià)格為1.49美元
book["avocado"] = 1.49
print(book)
{'avocado': 1.49, 'apple': 0.67, 'milk': 1.49}
5.3 應(yīng)用案例：
將散列表用于查找
電話本可以通過散列表來實(shí)現(xiàn)。查找速度近于O(1)時(shí)間浑度。
電話本需要提供如下功能：
- 添加聯(lián)系人及其電話號(hào)碼寇窑。
- 通過輸入聯(lián)系人來獲悉其電話號(hào)碼。
簡單點(diǎn)來說箩张，用python中的字典來創(chuàng)建這樣一個(gè)電話本再合適不過甩骏。
防止重復(fù)
向列表中增加數(shù)據(jù)時(shí)，先檢查是否在散列表中即可伏钠。
# 一個(gè)防止重復(fù)投票的案例横漏。
voted = {}
def check_voter(name):
if voted.get(name):
print "kick them out!"
else:
voted[name] = True
print "let them vote!"
>>> check_voter("tom")
let them vote!
>>> check_voter("mike")
let them vote!
>>> check_voter("mike")
kick them out!
將散列表用作緩存
即把用戶經(jīng)常重復(fù)發(fā)起的一些請(qǐng)求（如登錄前頁面）以散列表的形式存在本地，當(dāng)用戶發(fā)起請(qǐng)求時(shí)熟掂，先從該散列表中查詢是否已在本地缎浇，在則不需傳至服務(wù)器端處理。
