python快速排序的運(yùn)作過程

運(yùn)作過程

1、從數(shù)列中挑出一個(gè)元素，稱為基準(zhǔn)，重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面。

所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面(相同的數(shù)可以到任一邊)。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)操作。

2、小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

3、遞歸的最底部情形，是數(shù)列的大小是零或一。

也就是永遠(yuǎn)都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個(gè)算法總會(huì)結(jié)束，因?yàn)樵诿看蔚牡?，它至少?huì)把一個(gè)元素?cái)[到它最后的位置去。

實(shí)例

#快速排序-遞歸

defquick_sort(alist,begin,end):

#遞歸的終止條件是begin>=last,即數(shù)組大小為1或0

#遞歸終止時(shí)，數(shù)組已經(jīng)排好序了

ifbegin>=end:

return

else:

#以開頭的值作為基準(zhǔn)值，然后以基準(zhǔn)值為界將數(shù)組分區(qū)，將分區(qū)后的左右兩部分繼續(xù)調(diào)用快速排序函數(shù)

mid_value=alist[begin]

low=begin

high=end

#分別從右往左尋找小于基準(zhǔn)值的值，從左往右尋找大于基準(zhǔn)值的值

whilelow

#從右往左尋找小于基準(zhǔn)值的值

whilelow=mid_value:

high-=1

alist[low]=alist[high]

#從左往右尋找大于基準(zhǔn)值的值

whilelow

low+=1

alist[high]=alist[low]

#循環(huán)結(jié)束時(shí)，low==high，這個(gè)位置正是基準(zhǔn)點(diǎn)的位置

alist[low]=mid_value

#對(duì)low左邊的元素執(zhí)行快速排序

quick_sort(alist,begin,low-1)

quick_sort(alist,low+1,end)

if__name__=='__main__':

alist=[54,26,93,17,77,31,44,55,20]

print(alist)

quick_sort(alist,0,len(alist)-1)

print(alist)

以上就是python快速排序的運(yùn)作過程，希望對(duì)大家有所幫助。更多Python學(xué)習(xí)教程請(qǐng)關(guān)注IT培訓(xùn)機(jī)構(gòu):千鋒教育。