[笔记]《算法图解》第四章 快速排序分而治之(divide and conquer, D&C)D&C的工作原理快速排序代码实现小结

分而治之(divide and conquer, D&C)

一种著名的递归式问题解决方法。

D&C的工作原理

• 找出简单的基线条件

• 确定如何缩小问题的规模，使其符合基线条件。

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

快速排序

• 实现快速排序时,请随机地选择用作基准值的元素。
• 快速排序的平均运行时间为O(n log n)。
• 大O表示法中的常量有时候事关重大,这就是快速排序比合并排序快的原因所在。
• 比较简单查找和二分查找时,常量几乎无关紧要, 因为列表很长时, O(log n)的速度比O(n)快得多。

代码实现

def quicksort(array):
    if len(array) < 2:
        return array
    # 基线条件:为空或只包含一个元素的数组是“有序”的
else:
    pivot = array[0]
    # 递归条件:由所有小于基准值的
    less = [i for i in array[1:] if i <= pivot]
    # 元素组成的子数组
    greater = [i for i in array[1:] if i > pivot]
    # 由所有大于基准值的元素组成的子数组
    return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([10, 5, 2, 3]))

小结

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