三路快排也是用來解決序列中存在大量重復元素的問題，比雙路快排更高效
將序列分為三個部分，小于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]