快速排序

发表于 更新于 分类于
快速排序，暨leetcode 75. 颜色分类

快速排序

核心原理

快速排序的核心思想，就是从一个序列中，抽取一个做为基准。目标是一轮之后，基准元素放到它应该被放到的位置（它左方的所有元素都比它小或者相等，右方的所有元素都比它大或者相等）。

Overview实现概述

首先我们需要两个指针，left和right，指定我们现在左边界和右边界。
提取array[left]赋值作为pivot（基准），开始while循环
循环条件left < right:

  1. 如果array[right]>=pivot,右边界不断往左缩减，因为pivot右边的数都应该大于等于pivot，而大于等于的情况下，不需要动
  2. 退出step 1的时候，说明我们找到了一个应该放在pivot左边的数（但是现在它被放在了右边）。而因为我们array[left]赋值作为pivot，其实array[left]已经是没用的了，把array[right]赋值给array[left]
  3. 如果array[left]<=pivot,左边界不断往右扩展，因为pivot左边的数都应该小于等于pivot，而小于等于的情况下，不需要动
  4. 退出step 3的时候，说明我们找到了一个应该放在pivot右边的数（但是现在它被放在了左边）。而因为我们array[right]在step2的时候已经被拿走了，其实array[right]已经是没用的了，把array[left]赋值给array[right]

退出循环说明left==right，基准应该放的位置已经被确定了。把pivot赋值给array[left]

然后把pivot左边作为子序列一，继续重复这个过程，右边作为子序列二，也重复这个过程。

样例代码

partition

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def partition(array, left, right):
    if left >= right:
        return
    start_left = left
    start_right = right
    pivot = array[left]
    while left < right:
        while array[right] >= pivot and left < right:
            right -= 1
        array[left] = array[right]
        while array[left] <= pivot and left < right:
            left += 1
        array[right] = array[left]
    array[left] = pivot
    partition(array, start_left, left-1)
    partition(array, left+1, start_right)

main.py

1
2
3
4
array1 = [2,0,2,1,1,0]
print(array1)
partition(array1, 0, len(array1)-1)
print(array1)

时间复杂度

每一轮要对比n次，所以每一轮的复杂度是O(n)
一共需要O(log n)轮，所以是O(n log n)

LeetCode 75. 颜色分类

题目描述

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。

示例 1：

1
2
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

1
2
输入：nums = [2,0,1]
输出：[0,1,2]

示例 3：

1
2
输入：nums = [0]
输出：[0]

示例 4：

1
2
输入：nums = [1]
输出：[1]

提示：

n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

进阶：

你可以不使用代码库中的排序函数来解决这道题吗？
你能想出一个仅使用常数空间的一趟扫描算法吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

因为要原地排序，所以快速排序是可以的。这道题目中限定了输入只能是0、1、2，所以其实应该是有别的trick可以使用，并不一定需要用快速排序的。但是为了复习快速排序，这里就用快速排序。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:

    def sortPartition(self, nums: List[int], left: int, right: int) -> None:
        if left >= right:
            return
        start_left = left
        start_right = right
        pivot = nums[left]
        while left < right:
            while nums[right] >= pivot and left < right:
                right -= 1
            nums[left] = nums[right]
            while nums[left] <= pivot and left < right:
                left += 1
            nums[right] = nums[left]
        nums[left] = pivot
        self.sortPartition(nums, start_left, left-1)
        self.sortPartition(nums, left+1, start_right)

    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        self.sortPartition(nums, 0, len(nums)-1)