快速排序是冒泡排序的一種改良，它是一種不穩(wěn)定排序，即時(shí)間復(fù)雜度從O（n）~O（n^2）桐猬，平均O（nlgn）。不過(guò)在很多算法題里面刽肠，如果要求的是O（n）時(shí)間復(fù)雜度溃肪，貌似也可以用快排。
快排和核心思想是分而治之音五，以及大小分到兩邊惫撰。也就是說(shuō)，進(jìn)行多趟排序放仗，每一次拿一個(gè)值出來(lái)润绎，比它小的放左邊撬碟，比它大的放右邊诞挨，然后對(duì)左右兩個(gè)區(qū)間迭代。
這里主要有幾個(gè)問(wèn)題：怎么選那個(gè)值呢蛤？怎么實(shí)現(xiàn)根據(jù)大小分堆惶傻？相等怎么辦？
首先看怎么選擇的問(wèn)題其障，其實(shí)沒(méi)有規(guī)定银室，簡(jiǎn)單的就選第一個(gè)，高級(jí)一點(diǎn)的就取范圍內(nèi)一個(gè)隨機(jī)下標(biāo)励翼。
然后是怎么分堆蜈敢，一般都通過(guò)雙指針實(shí)現(xiàn)。當(dāng)然如果不在意空間復(fù)雜度汽抚，也可以用兩個(gè)新數(shù)組一遍掃描下來(lái)裝抓狭。這里主要講雙指針實(shí)現(xiàn)。假設(shè)區(qū)間范圍是0~n-1造烁，left=0,right=n-1,選擇的劃分下標(biāo)是p否过。具體做法：
- 先把n[p]值和最右端的換一個(gè)位置，這樣就相當(dāng)于把p拿出去了惭蟋。即nums[p], nums[right] = nums[right], nums[p]
- 兩個(gè)ij指針初始均指向最左邊苗桂。i每一次向后一步，遍歷整個(gè)區(qū)間告组。j只在i發(fā)現(xiàn)比n[p]小的元素時(shí)煤伟，交換元素后j+1
- 最后再把最右邊的n[p]放回來(lái)，此時(shí)和j指向的元素交換
- 對(duì)j的左右遞歸
極端情況：假設(shè)其余元素都大于p指向的元素，那么j動(dòng)不了持偏，最后遞歸nums[1:]驼卖，相當(dāng)于這一次只排序了一個(gè)元素；若其余所有元素都小于n[p]鸿秆，最后j指向最右端酌畜，還是只相當(dāng)于排序了一個(gè)元素。最理想的情況就是最后j指向中間卿叽，一次排序了一半元素桥胞。所以說(shuō)快排是不穩(wěn)定的。
關(guān)于取等號(hào)考婴，這其實(shí)也是很糾結(jié)的事情贩虾，比如對(duì)一個(gè)全部相等的序列快排，無(wú)論是相等放左邊也好不放也好沥阱，最后一次都只能排1個(gè)元素缎罢。不過(guò)即使這樣，對(duì)于相等的數(shù)排序效率也是O（n）考杉。
代碼：
from random import randint
def quickSort2(L, low, high):
if low >= high:
return L
p = randint(low, high)
key = L[p]
L[p], L[high] = L[high], L[p]
j = low
for i in range(low, high):
if L[i] < key:
L[i], L[j] = L[j], L[i]
j += 1
L[j], L[high] = L[high], L[j]
quickSort2(L, low, j - 1)
quickSort2(L, j + 1, high)
return L
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quickSort2(alist, 0, len(alist) - 1)
print(alist)
變形1：假如要排逆序呢策精？當(dāng)然可以先排正序然后逆序，不過(guò)其實(shí)在這里把L[i]<key改成大于就行了崇棠。
變形2：部分排序咽袜。假設(shè)只需要其中的正序前k個(gè)數(shù)，如何實(shí)現(xiàn)枕稀？當(dāng)然可以全部排序然后取出前k個(gè)询刹，不過(guò)那樣效率就不是最優(yōu)了。
考慮一次快排萎坷，把整個(gè)數(shù)組分成左邊假設(shè)n1個(gè)元素凹联，右邊n2個(gè)元素，則n1+n2+1=n哆档。
1.假如n1+1>=k蔽挠，也就是說(shuō)需要的區(qū)間全部在左邊，或者再加上中間這個(gè)已經(jīng)排好的元素虐呻，迭代轉(zhuǎn)到左半?yún)^(qū)的排序象泵；
2.否則，說(shuō)明左右半?yún)^(qū)都需要排斟叼，其中左邊都需要排偶惠，右邊也需要迭代，只不過(guò)右邊只需要找出前k-n1-1個(gè)元素即可朗涩。
代碼如下：
def quickSortK(L, low, high, k):
if low >= high:
return L
p = randint(low, high)
key = L[p]
L[p], L[high] = L[high], L[p]
j = low
for i in (range(low, high)):
if L[i] < key:
L[i], L[j] = L[j], L[i]
j += 1
L[j], L[high] = L[high], L[j]
if j - low >= k:
quickSortK(L, low, j - 1, k)
elif j - low + 1 == k:
quickSortK(L, low, j - 1, k - 1)
else:
quickSortK(L, low, j - 1, j - low + 1)
quickSortK(L, j+1, high, k - (j - low + 1))
return L
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quickSortK(alist, 0, len(alist) - 1, 9)
print(alist)
同樣忽孽，如果是想要找到前k大個(gè)元素，變一下比較符號(hào)即可。
