layout: posttitle: 数据结构与算法—快速排序
date: 2019-10-10
tag: 数据结构与算法

分而治之（divide and conquer， D&C）

  1. # 计算列表之和
  2. from typing import List
  4. def sumList(arr:List[int]) -> int:
  5.     if len(arr) == 0:
  6.         return 0
  7.     if len(arr) == 1:
  8.         return arr[0]
  9.     else:
  10.         return arr[0]+sumList(arr[1:])
  12. # 计算列表中的元素的个数
  13. def num_of_element(li):
  14.     if len(li) == 1:
  15.         return 1
  16.     else:
  17.         return 1 + num_of_element(li[1:])
  20. # 计算列表中的最大值
  21. def max_num(li):
  22.     if len(li) == 2:
  23.         return max(li)
  24.     else:
  25.         return max(li[0], max_num(li[1:]))
  26. max_num([1,2,3,5,6,7,8,9,9,11])

快速排序

  1. import random
  2. # 快速排序
  3. def quickSort(li):
  4.     if len(li) < 2:  # 当数组是空或者只有一个值时，不需要排序，只需返回结果即可
  5.         return li
  6.     else:
  7.         base = li[0] # 基准值
  8.         #　使用第一个为基准值，下面就 从 1 开始
  9.         less = [i for i in li[1:] if i <= base]
  10.         # 小于等于 要不然有重复的值会被过滤掉
  11.         greater = [i for i in li[1:] if i > base] 
  12.         return quickSort(less) + [base] + quickSort(greater)
  14. sample = [random.randrange(100) for i in range(5)]
  15. print(sample)
  16. print(quickSort(sample))
  1. # 随机选择基值
  2. import random
  3. # 快速排序
  6. def quickSort(li):
  7.     if len(li) < 2: # 当数组是空或者只有一个值时，不需要排序，只需返回结果即可
  8.         return li
  9.     else:
  10.         idx = random.randrange(0, len(li))
  11.         base = li[idx]  # 随机选择基准值
  12.         less = [i for i in li[:idx] + li[idx + 1:] if i <= base]
  13.         #　随机选择基准值，索引的时候去掉基准值，小于等于确保重复的值不被过滤
  14.         greater = [i for i in li[:idx] + li[idx + 1:] if i > base]
  15.         #print((idx, less, greater))
  16.         return quickSort(less) + [base] + quickSort(greater)
  19. sample = [1, 2, 1, 2, 3]
  20. print((quickSort(sample)))

再谈大 O 表示

快速排序的独特之处在于，其速度取决于选择的基准值。

快速排序 - 图1

最糟情况和平均情况

以上面的快速排序为例，若递归时基准值总是取最小或者最大，那么它左右两边总有一边是空，一边包含全部值，如下图，这时调用栈的高度会非常大，这是最糟情况。此时该算法的复杂度是 O(快速排序 - 图2)
快速排序 - 图3

若快速排序算法选择的基准值是每次列表中中间的那一个，那么调用的栈会比较短，每次都将数组分成两半，所以不需要太多次的递归调用就能达到基线条件。此时对应的是最佳情况，时间复杂度为 O(快速排序 - 图4)
快速排序 - 图5

最佳情况也是平均情况。只要你每次都随机地选择一个数组元素作为基准值，快速排序的平均运行时间就将为 O(快速排序 - 图6)。快速排序是最快的排序算法之一，也是 D&C 典范。

小结

  • D&C 将问题逐步分解。使用 D&C 处理列表时，基线条件很可能是空数组或只包含一个元素的数组。

  • 实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为
    O(n log n)。

  • 大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。

  • 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时， O(log n) 的速度比 O(n) 快得多。