基本思想

分治法。
分解：将数组A[p..r]分成A[p..q-1]和A[q+1..r]两部分，其中左数组中所有元素小于等于A[q]，右边所有元素大于A[q]。
解决：递归调用快速排序
合并：由于是原地排序，所以不用合并

具体实现

  1. def partition(nums: List, p, r):
  2.     key = nums[r]
  3.     i = p - 1
  4.     for j in range(p, r):
  5.         if nums[j] <= key:
  6.             i += 1
  7.             nums[i], nums[j] = nums[j], nums[i]
  8.     nums[i+1], nums[r] = nums[r], nums[i+1]
  9.     return i + 1
  11. def _quick_sort(nums: List, p , r):
  12.     if p < r:
  13.         q = partition(nums, p, r)
  14.         _quick_sort(nums, p, q-1)
  15.         _quick_sort(nums, q+1, r)
  17. def quick_sort(nums: List):
  18.     length = len(nums)
  19.     _quick_sort(nums, 0, length-1)

性能分析

平均时间复杂度：

  • 快速排序 - 图1

最坏时间复杂度：

  • 快速排序 - 图2

空间复杂度：

  • 快速排序 - 图3

    优化

  1. 对小数组使用归并排序。
  2. 后面再写
  3. 后面再写