序列元素重復(fù)，是序列已經(jīng)排好序的一種特殊情況，如果一個(gè)序列中的元素全部相同，也將出現(xiàn)最差情況。
如果序列中存在大量重復(fù)元素，在普通快排中，相等的元素會(huì)被全部放到分區(qū)點(diǎn)的一邊，這樣會(huì)大大增加快排的時(shí)間復(fù)雜度，雙路快排就是用來解決這個(gè)問題的。
能夠?qū)⑿蛄芯夥珠_的分區(qū)點(diǎn)才是好的分區(qū)點(diǎn)。均勻分開意味著保持O(logn)的復(fù)雜度。

from random import shuffle, randrange

def quick_sort(lst, left, right):
    # 當(dāng)只有一個(gè)元素的時(shí)候退出遞歸
    if left < right:
        p = partition(lst, left, right)
        # 左右分區(qū)分別遞歸
        quick_sort(lst, left, p)
        quick_sort(lst, p+1, right)

def partition(lst, left, right):
    rand = randrange(left, right)
    lst[left], lst[rand] = lst[rand], lst[left]   # 隨機(jī)挑選出一個(gè)元素，與第一個(gè)元素交換，作為分區(qū)點(diǎn)
    pivot = lst[left]    # 以第一個(gè)元素為分區(qū)點(diǎn)
    leftpos = left + 1
    rightpos = right - 1
    while leftpos <= rightpos:
        while leftpos <= rightpos and lst[leftpos] <= pivot:
            leftpos += 1
        while leftpos <= rightpos and lst[rightpos] >= pivot:
            rightpos -= 1
        if leftpos > rightpos:
            break
        lst[leftpos], lst[rightpos] = lst[rightpos], lst[leftpos]
    # 將pivot放入分區(qū)點(diǎn)
    lst[leftpos-1], lst[left] = lst[left], lst[leftpos-1]
    # 返回分區(qū)點(diǎn)索引
    return leftpos-1


source = list(range(10))
shuffle(source)
print(source)

quick_sort(source, 0, len(source))
print(source)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]