快速排序(Insertion Sort)也是一種遞歸排序算法。
快速排序原理：先以清單中的任意一個數為基準(一般選頭或尾)，将清單分為左、右兩個子清單。
左子清單的數要比基準數小，右子清單的數要比基準數大。然後繼續把左子清單和右子清單按同樣的方法繼續分解、比較，直到分無可分。最後将左子清單(比基準數小)+基準數+右子清單(比基準數大)連接配接起來得到一個有序數列。
以數列[3,5,8,1,2,9,4,7,6]為例，最初的數列順序如上圖所示。
第一次分組：以最後一個元素6為基準将數列分成兩組。分别從左右兩端周遊數列，比6小的分在左邊，比6大的分在右邊。先從左向右周遊，當遇到比6大的元素時将該元素放到右邊。同理從右向左周遊時，遇到比6小的元素放到左邊。當全部元素被周遊之後，将左邊數列，元素6，右邊數列按順序拼接成新的數組，此時元素6的位置固定。
遞歸處理左邊子數列：以最後一個元素2為基準，比2小的分在左邊子數列中，比2大的分在右邊子數列中經過一輪分組後，元素2的位置已經固定，接下來繼續遞歸的調用上述過程……
遞歸處理右邊子數列：以最後一個元素9為基準，比9小的分在左邊子數列中，比9大的分在右邊子數列中經過一輪分組後，隻會分成一組【8，7】，再次遞歸處理【8，7】，至此排序完畢。
快速排序的程式quicksort.py的代碼如下：
def quicksort(ilist):
less = [] # 小于基準元素的放到這個清單中
equal = [] # 等于基準元素的放到這個清單中
greater = [] # 大于基準元素的放到這個清單中
if len(ilist) > 1:
pivot = ilist[len(ilist)-1] # 取數組最後一個元素作為基準元素
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 測試快速排序方法，代碼如下：