原理

快速排序使用分治法(Divideandconquer)策略來把一個(gè)序列(list)分為兩個(gè)子序列(sub-lists)。

步驟

從數(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ù)列排序。

代碼

普通版

defquick_sort(list):

less=[]

pivotList=[]

more=[]

#遞歸出口

iflen(list)<=1:

returnlist

else:

#將第一個(gè)值做為基準(zhǔn)

pivot=list[0]

foriinlist:

#將比急轉(zhuǎn)小的值放到less數(shù)列

ifi

less.append(i)

#將比基準(zhǔn)打的值放到more數(shù)列

elifi>pivot:

more.append(i)

#將和基準(zhǔn)相同的值保存在基準(zhǔn)數(shù)列

else:

pivotList.append(i)

#對less數(shù)列和more數(shù)列繼續(xù)進(jìn)行排序

less=quick_sort(less)

more=quick_sort(more)

returnless+pivotList+more

咳咳，下面這段代碼出自《Pythoncookbook第二版》傳說中的三行實(shí)現(xiàn)python快速排序。

defqsort(arr):

iflen(arr)<=1:

returnarr

else:

pivot=arr[0]

less=[xforxinarr[1:]ifx

greater=[xforxinarr[1:]ifx>=pivot]

returnqsort(less)+[pivot]+qsort(greater)

當(dāng)然還有一行語法糖版本:

qs=lambdaxs:((len(xs)<=1and[xs])or[qs([xforxinxs[1:]ifx=xs[0]])])[0]

是不是感受到了Python的魅力?

以上內(nèi)容為大家介紹了python快速排序，希望對大家有所幫助，如果想要了解更多Python相關(guān)知識(shí)，請關(guān)注IT培訓(xùn)機(jī)構(gòu):千鋒教育。