快速排序

快速排序的核心思路需要结合二叉树的前序遍历 来理解：在二叉树遍历的前序位置将一个元素排好位置，然后递归地将剩下的元素排好位置。

快速排序核心思路

快速排序的基本思路是这样的：

1、在 nums 数组中任意选择一个元素作为切分元素 pivot（一般选择第一个元素）。

 [4, 1, 7, 2, 8, 5, 3, 6, 9]
  ^
pivot

2、对数组中的元素进行若干交换操作，将小于 pivot 的元素放到 pivot 的左边，大于 pivot 的元素放到 pivot 的右边（换句话说，其实就是将 pivot 这一个元素排好序）。

[3, 1, 2, 4, 8, 5, 7, 6, 9]
          ^
        pivot    

3、递归地对 pivot 左边和右边的子数组进行快速排序。

 [3, 1, 2] [4] [8, 5, 7, 6, 9]
  ^         ^   ^
pivot1          pivot2

 [1, 2, 3] [4] [5, 7, 6, 8, 9]
        ^   ^            ^
    pivot1             pivot2

4、递归地重复上述操作，直到所有元素都放到正确的位置：

[1] [2] [3] [4] [5] [6] [7] [8] [9]

快速排序的实现

• 代码框架

  def sort(nums: List[int], lo: int, hi: int):
  if lo >= hi:
      return
  # ****** 前序位置 ******
  # 对 nums[lo..hi] 进行切分，将 nums[p] 排好序
  # 使得 nums[lo..p-1] <= nums[p] < nums[p+1..hi]
  p = partition(nums, lo, hi)
  
  # 去左右子数组进行切分
  sort(nums, lo, p - 1)
  sort(nums, p + 1, hi)

• 具体代码

  from typing import List
  
  def sort(nums: List[int], lo: int, hi: int):
      if lo >= hi:
          return
      # ****** 前序位置 ******
      # 对 nums[lo..hi] 进行切分，将 nums[p] 排好序
      # 使得 nums[lo..p-1] <= nums[p] < nums[p+1..hi]
      p = partition(nums, lo, hi)
  
      # 去左右子数组进行切分
      sort(nums, lo, p - 1)
      sort(nums, p + 1, hi)
  
  def partition(nums: List[int], lo: int, hi: int) -> int:
      pivot = nums[lo]
      left = lo + 1
      right = hi
  
      while True:
          while left <= right and nums[left] < pivot:
              left += 1
          while left <= right and nums[right] > pivot:
              right -= 1
  
          if left > right:
              break
  
          nums[left], nums[right] = nums[right], nums[left]
  
      nums[lo], nums[right] = nums[right], nums[lo]
      return right

时间复杂度

快速排序的平均时间复杂度为$O(n\log n)$，最坏情况时间复杂度为$O(n^2)$。

空间复杂度

快速排序不需要额外的辅助空间，是原地排序算法。

递归遍历二叉树时，递归函数的堆栈深度为树的高度，所以空间复杂度是$O(n\log n)$

稳定性

快速排序是不稳定排序算法，因为在 partition 函数中，不会考虑相同元素的相对位置，所以相同元素的相对位置可能会发生变化。