三路快排
三路快排也是用來解決序列中存在大量重復元素的問題,比雙路快排更高效
將序列分為三個部分,小于pivot、等于pivot、大于pivot
等于pivot的部分不遞歸,這樣在存在大量重復元素時,將大大縮小遞歸的數據規模
from random import shuffle, randint
def quick_sort(lst, left, right):
if left < right: # 當只有一個元素的時候退出遞歸
rand = randint(left, right)
lst[left], lst[rand] = lst[rand], lst[left] # 隨機挑選出一個元素,與第一個元素交換,作為分區點
pivot = lst[left] # 以第一個元素為分區點
leftpos = left # lst[left+1...lt] < v
rightpos = right + 1 # lst[gt...right] > v
i = left + 1 # lst[lt+1...i] == v
while i < rightpos:
if lst[i] < pivot:
lst[leftpos + 1], lst[i] = lst[i], lst[leftpos + 1]
leftpos += 1
i += 1
elif lst[i] > pivot:
lst[rightpos - 1], lst[i] = lst[i], lst[rightpos - 1]
rightpos -= 1
else:
i += 1
lst[leftpos], lst[left] = lst[left], lst[leftpos]
leftpos -= 1
quick_sort(lst, left, leftpos)
quick_sort(lst, rightpos, right)
source = list(range(10))
shuffle(source)
quick_sort(source, 0, len(source) - 1)
print(source)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
浙公網安備 33010602011771號