遞歸排序算法快速排序的實現(xiàn)過程

快速排序(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

測試快速排序方法，代碼如下：