《算法图解》2

四、快速排序

分而治之DC（divide and conquer）（递归式问题解决方法）：快速排序

DC原理：

找出简单的基线条件

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

快速排序：寻找基准值；将数组分成两个子数组；对子数组进行快速排序

复杂度：O（NlogN）

选择数组第一个元素作为基准值：

快递排序代码：

1 def quicksort(array):
2     if len(array) <2:
3         return array
4     else:
5         pivot = array[0]
6         less = [i for i in array[1:] if i <= pivot]
7         greater = [i for i in array[1:] if i > pivot]
8         return quicksort(less) + [pivot] + quicksort(greater)
9 print(quicksort([10, 5, 2, 3, 7, 13]))

还有一种数组sum求和，利用递归来实现？？how??

;;;;;;;;;;;;

四、散列表

也是一种数据结构

散列表检查是否重复速度非常快。

code(用来避免重复):

 1 voted = {}
 2 def check_voter(name):
 3     if voted.get(name):
 4         print ("kick them out!")
 5     else:
 6         voted[name] = True
 7         print ("let them vote!")
 8 
 9 check_voter("tom")
10 check_voter("tom")

。