快速排序

题目连接： 912. 排序数组

代码 (三路快排)

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        self.quick_sort(nums, 0, len(nums) - 1)
        return nums

    def quick_sort(self, nums: List[int], left: int, right: int) -> None:
        if left >= right:
            return
        le, gt = self.partition(nums, left, right)
        self.quick_sort(nums, left, le - 1)
        self.quick_sort(nums, gt, right)
    
    def partition(self, nums: List[int], left: int, right: int):
        random_index = random.randint(left, right)
        nums[random_index], nums[left] = nums[left], nums[random_index]
        pivot = nums[left]
        
        # 循环不变量：
        # [left, le - 1] < pivot
        # [le, i] = pivot
        # [gt, right] > pivot
        le = left
        gt = right + 1
        i = left + 1
        while i < gt:
            if nums[i] < pivot:
                nums[i], nums[le] = nums[le], nums[i]
                le += 1
                i += 1
            elif nums[i] == pivot:
                i += 1
            else:
                gt -= 1
                nums[i], nums[gt] = nums[gt], nums[i]
        return le, gt

三路快排

思想：把整个数组分成三个部分，引入两个指针，le (less equal) 和 gt (great than)

此时有:

1. nums[left, le - 1] 均小于 V
2. nums[gt, right] 均大于 V

初始值:

• le = left
• gt = right + 1

遍历指针 i 从 left + 1 开始

1. 遇到比 V 小的，交换 (le, i)，le、i 均后移一位
2. 遇到等于 V 的，不用交换，i 后移一位
3. 遇到比 V 大的，gt 前移一位，交换 (gt, i)
   • 注意：此时 i 不能后移，因为交换过来的 nums[gt] 之前未看过

现在考虑退出循坏的条件，i 碰到 gt 即可

不要取 “=”，因为 i 没看过，表示下一个要看，gt 的值都看过了，故 while i < gt

循环停止时

此时有:

1. nums[left, le - 1] 均小于 V
2. nums[gt, right] 均大于 V
3. nums[le, gt - 1] 均等于 V

返回 le, gt, 并回到 quick_sort 函数

• 递归调用左区间 [left, le - 1]
• 递归调用右区间 [gt, right]
• 直到排序完成