python快速排序的運作過程

運作過程

1、從數列中挑出一個元素，稱為基準，重新排序數列，所有元素比基準值小的擺放在基準前面。

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

2、小于基準值元素的子數列和大于基準值元素的子數列排序。

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

也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個算法總會結束，因為在每次的迭代中，它至少會把一個元素擺到它最后的位置去。

實例

#快速排序-遞歸

defquick_sort(alist,begin,end):

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

#遞歸終止時，數組已經排好序了

ifbegin>=end:

return

else:

#以開頭的值作為基準值，然后以基準值為界將數組分區，將分區后的左右兩部分繼續調用快速排序函數

mid_value=alist[begin]

low=begin

high=end

#分別從右往左尋找小于基準值的值，從左往右尋找大于基準值的值

whilelow

#從右往左尋找小于基準值的值

whilelow=mid_value:

high-=1

alist[low]=alist[high]

#從左往右尋找大于基準值的值

whilelow

low+=1

alist[high]=alist[low]

#循環結束時，low==high，這個位置正是基準點的位置

alist[low]=mid_value

#對low左邊的元素執行快速排序

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快速排序的運作過程，希望對大家有所幫助。更多Python學習教程請關注IT培訓機構:千鋒教育。