更新時間:2023-03-24 來源:黑馬程序員 瀏覽量:
快速排序(Insertion Sort)也是一種遞歸排序算法。
快速排序原理:先以列表中的任意一個數(shù)為基準(一般選頭或尾),將列表分為左、右兩個子列表。
左子列表的數(shù)要比基準數(shù)小,右子列表的數(shù)要比基準數(shù)大。然后繼續(xù)把左子列表和右子列表按同樣的方法繼續(xù)分解、比較,直到分無可分。最后將左子列表(比基準數(shù)小)+基準數(shù)+右子列表(比基準數(shù)大)連接起來得到一個有序數(shù)列。
以數(shù)列[3,5,8,1,2,9,4,7,6]為例,最初的數(shù)列順序如上圖所示。
第一次分組:以最后一個元素6為基準將數(shù)列分成兩組。分別從左右兩端遍歷數(shù)列,比6小的分在左邊,比6大的分在右邊。先從左向右遍歷,當(dāng)遇到比6大的元素時將該元素放到右邊。同理從右向左遍歷時,遇到比6小的元素放到左邊。當(dāng)全部元素被遍歷之后,將左邊數(shù)列,元素6,右邊數(shù)列按順序拼接成新的數(shù)組,此時元素6的位置固定。
遞歸處理左邊子數(shù)列:以最后一個元素2為基準,比2小的分在左邊子數(shù)列中,比2大的分在右邊子數(shù)列中經(jīng)過一輪分組后,元素2的位置已經(jīng)固定,接下來繼續(xù)遞歸的調(diào)用上述過程……
遞歸處理右邊子數(shù)列:以最后一個元素9為基準,比9小的分在左邊子數(shù)列中,比9大的分在右邊子數(shù)列中經(jīng)過一輪分組后,只會分成一組【8,7】,再次遞歸處理【8,7】,至此排序完畢。
快速排序的程序quicksort.py的代碼如下:
def quicksort(ilist): less = [] # 小于基準元素的放到這個列表中 equal = [] # 等于基準元素的放到這個列表中 greater = [] # 大于基準元素的放到這個列表中 if len(ilist) > 1: pivot = ilist[len(ilist)-1] # 取數(shù)組最后一個元素作為基準元素 for x in ilist: if x < pivot: # 小于基準元素的放到列表less中 less.append(x) elif x == pivot: # 等于基準元素的放到這個列表中 equal.append(x) elif x > pivot: # 大于基準元素的放到列表greater中 greater.append(x) return quicksort(less)+equal+quicksort(greater) # 將三部分拼接起來 else: # 只有一個元素的時候直接返回 return ilist
測試快速排序方法,代碼如下: