三路快排

快排图解

基础快排：

将区间分为两部分，小于等于 和 大于

双路快排：

将区间分为两部分，小于等于 和 大于等于，重复元素等概率的分配到这两部分中

三路快排：

三路快排又多加了一个指针，用于将区间分为三部分

二路快排是将与基准值相等的元素，等概率的分配到左右两部分

三路快排则是将与基准值相等的元素，集中在区间的中间部分(紧接小于基准值区间的右边)

arr[left] 基准值

arr[left + 1, lt] 小于基准值的区间

arr[lt+1, i - 1] 等于基准值的区间

arr[i, gt - 1] 暂未被遍历的区间

arr[gt, right] 大于基准值的区间

思路

三路快排基本思路：将区间分为三个部分（小于基准数， 等于基准数， 大于基准数）。将等于基准值的数集中在区间的中间。

边想边写

• 定义指针

def partition(arr, left, right):
    pivot = arr[left]
    lt = left
    gt = right + 1
    i = left + 1

• 遍历区间

从 left+1 开始遍历，即从 i 开始遍历，需要遍历到 right，所以循环条件是

i < right + 1 即 i < gt

def partition(arr, left, right):
    pivot = arr[left]
    lt = left
    gt = right + 1
    i = left + 1
    while i < gt:
        pass

• 小于基准数

lt表示的是，当前元素以及在区间arr[left+1...lt]的所有元素都小于基准值

此时 i 位置的值小于基准值，则应当将这个元素接在 lt的后面一位，所以有

lt += 1
arr[lt], arr[i] = arr[i], arr[lt]
i += 1

• 等于基准数

因为等于基准值的部分是紧接着 [left+1...lt] 的后面，当 i 遍历到 lt+1的位置时等于基准值，则不需要做什么，继续让 i 向后移动一位即可

• 大于基准数

既然此时 i 的值大于基准数，那么就可以将这个数与gt位置元素交换，将大的数换到右边部分

在交换之后，因为 交换之后i的值不确定大小，所以这里 i 就不进行移动了，而是在下一次循环中继续判断。

gt表示的是，在区间arr[gt...right]的所有元素都大于基准值

arr[i], arr[gt] = arr[gt], arr[i]
gt -= 1

切分函数完整代码

def partition(arr, left, right):
    pivot = arr[left]
    # 寻找小于基准数的指针
    lt = left
    # 寻找大于基准数的指针
    gt = right + 1
    
    i = left + 1
    while i < gt:
        if arr[i] < pivot:
            # 当前元素小于基准值
            lt += 1
            arr[lt], arr[i] = arr[i], arr[lt]
            i += 1
        elif arr[i] > pivot:
            # 当前元素大于基准值
            # 所以应该将这个元素移动至右边的部分
            gt -= 1
            arr[i], arr[gt] = arr[gt], arr[i]
        elif arr[i] == pivot:
            i += 1
    arr[left], arr[lt] = arr[lt], arr[left]
    return lt, gt

动图演示

完整代码

def partition(arr, left, right):

    # [left...lt] < pivot
    # [lt+1...i] = pivot
    # [gt...right] > pivot
    pivot = arr[left]
    lt = left
    gt = right + 1
    i = left + 1
    while i < gt:
        if arr[i] < pivot:
            lt += 1
            arr[i], arr[lt] = arr[lt], arr[i]
            i += 1
        elif arr[i] == pivot:
            i += 1
        elif arr[i] > pivot:
            gt -= 1
            arr[i], arr[gt] = arr[gt], arr[i]
    # 基准值与小部分的最后一个元素值进行交换
    arr[left], arr[lt] = arr[lt], arr[left]
    return lt, gt


def quick_sort(arr, left, right):

    if left >= right:
        return

    lt, gt = partition(arr, left, right)
    # 在有很多重复元素的排序任务中，lt 和 gt 可能会相距很远
    # 因此后序递归调用的区间变小
    # 递归的深度也大大降低了
    quick_sort(arr, left, lt - 1)
    quick_sort(arr, gt, right)