快速排序

Posted on | In

分而治之 D&C

D&C的工作原理：（一种解决问题的思路）

  • 找出简单的基线条件
  • 确定如何缩小问题的规模，使其符合基线条件
    举例：
    给定一个数组[2,3,4]，需要将这些数字相加并返回结果。使用循环可以很简单完成任务。
    1
    2
    3
    4
    5
    def sum(arr):
      total = 0
      for x in arr:
        total = total + x
      return total

如果使用递归函数，则需要先找出基线条件，并且每次递归调用都必须离空数组更进一步。

1
2
3
4
5
def sum(arr):
  if len(arr) == 0:
    reuturn 0
  else:
    return arr[0]+sum(arr[1:])

快速排序

对给定的数组进行快速排序：首先选取一个基准值，然后以基准值为分界线，左边是一个数组，右边是另一个数组。然后对数组再次进行快速排序，直到左右的数组长度小于等于1.
[3,1,2,4,5]
选择第一个元素3为基准值，数组被分成了3块，[1,2]+[3]+[4,5]
对于数组元素大于1的数组再次确认基准值并分组，直到所有的数组元素都只有一个，这是所有的数据组合起来就是一个有序的数组。

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
#个人代码
def sort(arr):
  left_arr = []
  right_arr = []
  mid_arr = []
  if len(arr) <= 1:
    return arr
  else:
    mid_arr.append(arr[0])
    for x in arr[1:]:
      if x > arr[0]:
        right_arr.append(x)
      elif x < arr[0]:
        left_arr.append(x)
      elif x == arr[0]:
        mid_arr.append(x)
    return sort(left_arr)+ mid_arr +sort(right_arr)
#书本代码
def quick_srot(arr):
  if len(arr) < 2:
    return arr
  else:
    pivot = arr[0]
    less = [i for i in arr[1:] if i <= pivot]
    more = [i for i in arr[1:] if i > pivot]
    return quick_sort(less) + pivot + quick_sort(more)

时间复杂度

快速排序的时间复杂度是不一定的，最好情况下为O(nlog n)，最坏情况下为O(n^2)
合并排序的时间复杂度是O(nlog n)

合并排序和快速排序比较

一般时间复杂度相同的算法，消耗的时间差距也是不一样的，因为n只是变量，实际的时间复杂度应该还存在一个c常量。c是算法所需的固定时间常量。但是一般情况下，常量对于速度没有太大影响，但是有时候也会有很大影响。
合并排序和快速排序的时间复杂度都是O(nlog n)，但是快速排序的性能高度依赖于你选择的基准值，如果每次选择第一个元素为基准值，即使数组已经是有序的，但是依然会对其进行排序。这种是最坏的情况。最好的情况是每次都能以中间值作为基准值，这个时候时间复杂度就是O(n) x O(log n) = O(nlog n)。

小结

  • D&C将问题逐步分解，使用D&C处理列表时，极限条件可能是一个空数组或只包含了一个元素的数组。
  • 实现快速排序时，请随机选择元素作为基准值，快速排序的平均运行时间为O(nlog n)
  • 大O表示法中的常量有时事关重大，这就是快速排序比合并排序快的原因
  • 比较简单查找和二分超赵的时候，常量几乎无关紧要，因为列表很长，O(log n)的速度比O(n)快得多