原理

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

步驟

從數列中挑出一個元素，稱為”基準”(pivot)，

重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面(相同的數可以到任一邊)。在這個分區結束之后，該基準就處于數列的中間位置。這個稱為分區(partition)操作。

遞歸地(recursive)把小于基準值元素的子數列和大于基準值元素的子數列排序。

代碼

普通版

defquick_sort(list):

less=[]

pivotList=[]

more=[]

#遞歸出口

iflen(list)<=1:

returnlist

else:

#將第一個值做為基準

pivot=list[0]

foriinlist:

#將比急轉小的值放到less數列

ifi

less.append(i)

#將比基準打的值放到more數列

elifi>pivot:

more.append(i)

#將和基準相同的值保存在基準數列

else:

pivotList.append(i)

#對less數列和more數列繼續進行排序

less=quick_sort(less)

more=quick_sort(more)

returnless+pivotList+more

咳咳，下面這段代碼出自《Pythoncookbook第二版》傳說中的三行實現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)

當然還有一行語法糖版本:

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

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

以上內容為大家介紹了python快速排序，希望對大家有所幫助，如果想要了解更多Python相關知識，請關注IT培訓機構:千鋒教育。