第四章 快速排序
分而治之
这个概念是书中一直提到的, 个人理解就是把问题分解出来, 抽出来一小块一小块解决
递归
第三章就讲到递归了, 两个关键点找出基线条件和递归条件
记得之前写过一个妹纸图爬虫, 主要就是用的递归调取本身, 来爬取下一页的图片。 整个站都可以爬下来, 前提是网站反爬不厉害...
快速排序
简称快排, 一种排序算法。 在平均情况下, 排序 n 个项目要 O(nlogn)。 最坏的情况下则需要 O(n2)。 事实上，快速排序 O(nlogn) 通常明显比其他算法更快, 因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成
代码:
# coding: utf-8
"""
快速排序
"""
def quick_sort(arr):
if len(arr) < 2:
return arr
else:
temp = arr[0]
less = [i for i in arr[1:] if i < temp]
greater = [i for i in arr[1:] if i > temp]
return quick_sort(less) + [temp]+ quick_sort(greater)
arr = [32, 4, 54, 65, 5, 864]
print(quick_sort(arr))
小结
- 分而治之将问题逐步分解. 使用分而治之处理列表的时候, 基线条件可能是空数组或只包含一个元素的数组
- 实现快速排序, 请随机的选择用作基准值的元素。 快速排序的平均运行时间 O(nlogn)
