青青草碰碰,黄色av特区网站

快速排序，面試必問題。面試百度時(shí)三次面試被問到快排，本以為掌握的很好，但細(xì)節(jié)方面還是不到位，發(fā)揮的不是很好，特此記錄，勉勵(lì)自己。

問題：為什么是nlog(n),n怎么來(lái)，log(n)怎么來(lái)

快速排序
快速排序是應(yīng)用最廣泛的排序算法，基本思路是：將一個(gè)數(shù)組分成兩個(gè)子數(shù)組,將兩部分獨(dú)立排序,當(dāng)兩個(gè)子數(shù)組都有序時(shí),整個(gè)數(shù)組也就有序了，這與歸并排序有所不同，歸并排序中，將一個(gè)數(shù)組分成兩個(gè)數(shù)組后，需要對(duì)兩個(gè)子數(shù)組進(jìn)行歸并，在歸并的過(guò)程中排序，而快速排序是在將一個(gè)數(shù)組分成兩個(gè)數(shù)組的過(guò)程中進(jìn)行排序，當(dāng)分到盡頭的時(shí)候，數(shù)組就已經(jīng)有序了，不需要再進(jìn)行其它任何操作
快速排序中重點(diǎn)是找到將一個(gè)數(shù)組分為兩個(gè)數(shù)組的切分點(diǎn)，在歸并排序中，其實(shí)也是有這樣的切分點(diǎn)的，就是 mid，也就是說(shuō)歸并排序默認(rèn)將一個(gè)數(shù)組等分，而在快速排序中，對(duì)一個(gè)數(shù)組的切分，并不一定是等分，需要根據(jù)具體的切分點(diǎn)的位置來(lái)進(jìn)行切分，所以，找到合適的切分點(diǎn)的位置是很重要的，直接影響到整個(gè)排序的性能。
尋找切分點(diǎn)
切分點(diǎn)需要滿足三個(gè)條件：(假設(shè)切分點(diǎn)索引為 k)
對(duì)于某個(gè)索引 k,數(shù)組中對(duì)應(yīng)索引的值 a[k] 是確定的
數(shù)組索引[lo,k-1] (即切分點(diǎn)左邊的所有元素) 中的所有元素的值都不大于切分點(diǎn)元素的值( <= )
數(shù)組索引[k+1,hi] (即切分點(diǎn)右邊的所有元素) 中的所有元素的值都不小于切分點(diǎn)元素的值( >= )

假設(shè)有一組數(shù)：

尋找切分點(diǎn)的過(guò)程是：(其中 lo 為數(shù)組最低位索引，hi 為數(shù)組最高位索引，從左往右遍歷的指針為 i，從右往左遍歷的指針為 j)
取 a[lo] 的值作為初始切分點(diǎn)元素的值，即切分點(diǎn)索引為 0，值為 16

從數(shù)組左端向右遍歷[1,5]，當(dāng)遇到一個(gè)大于等于切分點(diǎn)的元素，即索引為 2 的元素，停止遍歷，此時(shí) i=2

從數(shù)組右端向左遍歷[5,0]，當(dāng)遇到一個(gè)小于等于切分點(diǎn)的元素，即索引為 5 的元素，停止遍歷，此時(shí) j=5

交換 i 和 j 對(duì)應(yīng)的值，交換后:

從數(shù)組左端向右遍歷[3,5]，當(dāng)遇到一個(gè)大于等于切分點(diǎn)的元素，即索引為 5 的元素，停止遍歷，此時(shí) i=5

從數(shù)組右端向左遍歷[4,0]，當(dāng)遇到一個(gè)小于等于切分點(diǎn)的元素，即索引為 4 的元素，停止遍歷，此時(shí) j=4

當(dāng) i>=j 時(shí)停止循環(huán)，不會(huì)執(zhí)行 i 和 j 的交換，而是將切分點(diǎn)元素和 j 元素交換，交換后:

到此，尋找第一個(gè)切分點(diǎn)完成，切分點(diǎn)索引為 4，對(duì)應(yīng)的值為 16
找到切分點(diǎn)，接下來(lái)將數(shù)組按照切分點(diǎn)分成兩部分，從上面的執(zhí)行結(jié)果可以知道，數(shù)組將被分為 [0,3] 和 [5,5]，接下來(lái)就是對(duì) [0,3] 部分重復(fù)尋找切分點(diǎn)的過(guò)程：
取 a[lo] 的值作為初始切分點(diǎn)元素的值，即切分點(diǎn)索引為 0，值為 14

從數(shù)組左端向右遍歷[1,3]，當(dāng)遇到一個(gè)大于等于切分點(diǎn)的元素，沒有找到，遍歷到數(shù)組盡頭，此時(shí) i=3

從數(shù)組右端向左遍歷[3,0]，當(dāng)遇到一個(gè)小于等于切分點(diǎn)的元素，即索引為 3 的元素，停止遍歷，此時(shí) j=3

當(dāng) i>=j 時(shí)停止循環(huán)，不會(huì)執(zhí)行 i 和 j 的交換，而是將切分點(diǎn)元素和 j 元素交換，交換后:

到此，尋找第二個(gè)切分點(diǎn)完成，切分點(diǎn)索引為 3，對(duì)應(yīng)的值為 14

同理，數(shù)組將按照切分點(diǎn)分為 [0,2] 和[3,3]，接下來(lái)對(duì) [0,2] 部分重復(fù)尋找切分點(diǎn)：
取 a[lo] 的值作為初始切分點(diǎn)元素的值，即切分點(diǎn)索引為 0，值為 11

從數(shù)組左端向右遍歷[1,2]，當(dāng)遇到一個(gè)大于等于切分點(diǎn)的元素，即索引為 1 的元素，停止遍歷，此時(shí) i=1

從數(shù)組右端向左遍歷[2,0]，當(dāng)遇到一個(gè)小于等于切分點(diǎn)的元素，沒有找到，遍歷到數(shù)組起始位置，此時(shí) j=0

當(dāng) i>=j 時(shí)停止循環(huán)，不會(huì)執(zhí)行 i 和 j 的交換，而是將切分點(diǎn)元素和 j 元素交換，交換后:

到此，尋找第三個(gè)切分點(diǎn)完成，切分點(diǎn)索引為 0，對(duì)應(yīng)的值為 11
此時(shí)，由于切分點(diǎn)位置為 0，所以只能切分出一個(gè)子數(shù)組，即 [1,2]，繼續(xù)尋找切分點(diǎn)
取 a[lo] 的值作為初始切分點(diǎn)元素的值，即切分點(diǎn)索引為 1，值為 13