跳转至

手撕快速排序

约 267 个字 35 行代码 2 张图片 预计阅读时间 1 分钟

题目连接： 912. 排序数组

代码 (三路快排)

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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)

image.png

此时有:

  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

循环停止时

image.png

此时有:

  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]
  • 直到排序完成