快速排序
快速排序（英語(yǔ)：Quicksort）泌类，又稱劃分交換排序（partition-exchange sort）爆价，通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分顷蟆，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小蔽莱，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序窿侈，整個(gè)排序過程可以遞歸進(jìn)行饮潦，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
步驟為：
- 從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"（pivot）坞琴，
- 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面逗抑，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）剧辐。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置邮府。這個(gè)稱為分區(qū)（partition）操作荧关。
- 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
遞歸的最底部情形褂傀，是數(shù)列的大小是零或一忍啤，也就是永遠(yuǎn)都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個(gè)算法總會(huì)結(jié)束同波，因?yàn)樵诿看蔚牡╥teration）中鳄梅，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。
快速排序的分析
def quick_sort(alist, start, end):
"""快速排序"""
# 遞歸的退出條件
if start >= end:
return
# 設(shè)定起始元素為要尋找位置的基準(zhǔn)元素
mid = alist[start]
# low為序列左邊的由左向右移動(dòng)的游標(biāo)
low = start
# high為序列右邊的由右向左移動(dòng)的游標(biāo)
high = end
while low < high:
# 如果low與high未重合未檩，high指向的元素不比基準(zhǔn)元素小戴尸，則high向左移動(dòng)
while low < high and alist[high] >= mid:
high -= 1
# 將high指向的元素放到low的位置上
alist[low] = alist[high]
# 如果low與high未重合，low指向的元素比基準(zhǔn)元素小冤狡，則low向右移動(dòng)
while low < high and alist[low] < mid:
low += 1
# 將low指向的元素放到high的位置上
alist[high] = alist[low]
# 退出循環(huán)后孙蒙，low與high重合，此時(shí)所指位置為基準(zhǔn)元素的正確位置
# 將基準(zhǔn)元素放到該位置
alist[low] = mid
# 對(duì)基準(zhǔn)元素左邊的子序列進(jìn)行快速排序
quick_sort(alist, start, low-1)
# 對(duì)基準(zhǔn)元素右邊的子序列進(jìn)行快速排序
quick_sort(alist, low+1, end)
alist = [54,26,93,17,77,31,44,55,20]
quick_sort(alist,0,len(alist)-1)
print(alist)
時(shí)間復(fù)雜度
- 最優(yōu)時(shí)間復(fù)雜度：O(nlogn)
- 最壞時(shí)間復(fù)雜度：O(n2)
- 穩(wěn)定性：不穩(wěn)定
從一開始快速排序平均需要花費(fèi)O(n log n)時(shí)間的描述并不明顯悲雳。但是不難觀察到的是分區(qū)運(yùn)算挎峦，數(shù)組的元素都會(huì)在每次循環(huán)中走訪過一次，使用O(n)的時(shí)間合瓢。在使用結(jié)合（concatenation）的版本中坦胶，這項(xiàng)運(yùn)算也是O(n)。
在最好的情況歪玲，每次我們運(yùn)行一次分區(qū)迁央，我們會(huì)把一個(gè)數(shù)列分為兩個(gè)幾近相等的片段。這個(gè)意思就是每次遞歸調(diào)用處理一半大小的數(shù)列滥崩。因此岖圈，在到達(dá)大小為一的數(shù)列前，我們只要作log n次嵌套的調(diào)用钙皮。這個(gè)意思就是調(diào)用樹的深度是O(log n)蜂科。但是在同一層次結(jié)構(gòu)的兩個(gè)程序調(diào)用中，不會(huì)處理到原來數(shù)列的相同部分短条；因此导匣，程序調(diào)用的每一層次結(jié)構(gòu)總共全部?jī)H需要O(n)的時(shí)間（每個(gè)調(diào)用有某些共同的額外耗費(fèi)，但是因?yàn)樵诿恳粚哟谓Y(jié)構(gòu)僅僅只有O(n)個(gè)調(diào)用茸时，這些被歸納在O(n)系數(shù)中）贡定。結(jié)果是這個(gè)算法僅需使用O(n log n)時(shí)間。
快速排序演示
思考：
之前的插入排序和希爾排序可都，都是把序列看成兩組：有序+無序
快排就看某元素直接放在哪里缓待，直接找該元素位置，兩個(gè)游標(biāo)雙面夾擊渠牲。
找一個(gè)low游標(biāo)旋炒，再找一個(gè)high游標(biāo)。
讓low經(jīng)歷過的元素都比54小签杈，high經(jīng)過的元素都比54大瘫镇。
先把54放在最左邊，讓low游標(biāo)從第一個(gè)走，high游標(biāo)從最后一個(gè)走铣除。
本質(zhì)：找出第一個(gè)值作為參照谚咬，兩邊相夾找到這個(gè)元素的正確位置。把整個(gè)序列分成兩個(gè)部分通孽；這個(gè)過程過后序宦，該元素所在位置就是它應(yīng)該在的位置睁壁。
代碼分析：
*如果出現(xiàn)等于的情況背苦，盡量讓等于的那個(gè)值放在目標(biāo)值54的一邊
