《算法图解》第四章笔记与课后练习_快速排序算法

软件环境：Python 3.7.0b4

一、分而治之

工作原理：

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

# 4.2 def count(list):if list == []:return 0return 1 + count(list[1:])# 4.3 def max(list):if len(list) == 2:return list[0] if list[0] > list[1] else list[1]sub_max = max(list[1:])return list[0] if list[0] > sub_max else sub_max

 

4.4：二分查找的基线条件是数组只包含一个元素。如果要查找的值与这个元素相同，就找到了！否则说明它不在数组中。递归条件为 把数组分成两半，将其中一半丢弃，并对另一半执行二分查找。

 

二、快速排序

def quicksort(array):if len(array) < 2:# 基线条件：为空或只包含一个元素的数组是“有序”的return arrayelse:# 递归条件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])) # 需排序的数组

 

 

三、小结

• 分治法是将问题逐步分解。使用分治法处理列表时，基线条件很可能是空数组或只包含一个元素的数组。
• 实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O(nlog n)。

 

总结

以上是生活随笔为你收集整理的《算法图解》第四章笔记与课后练习_快速排序算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。