使用栈也存在一些缺点，存储详尽的信息可能占用大量的内存。每个函数调 用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。那么你只能使用循环完成或者尾递归（这个高级方法我还不会）。
快速排序 分而治之假设要将一块土地均匀分成方块，并且确保方块最大。可以使用D&C策略。D&C算法是递归的。
使用D&C解决问题的过程包括两个步骤：
(1) 找出基线条件，这种条件必须尽可能简单。
(2) 不断将问题分解（或者说缩小规模），直到符合基线条件。
根据D&C的定义，每次递归调用都必须 缩小问题的规模。这个问题的基线条件就是一条边的长度是另一条边的整数倍。以短边为基准，在长边取短边*n的最大取值，剩下的部分依次按上述操作，直到最后长边为短边的整数倍位置短边**2就是最大方形了。
D&C的工作原理：
(1) 找出简单的基线条件；
(2) 确定如何缩小问题的规模，使其符合基线条件。
D&C并非可用于解决问题的算法，而是一种解决问题的思路。
快速排序快速排序使用了D&C。对排序算法来说，基线条件为数组为空或只包含一个元素。
首先，从数组中选择一个元素，这个元素被称为基准值；
接下来，找出比基准值小的元素以及比基准值大的元素。
再对这两个子数组进行快速排序，直到满足基线条件。
注：归纳证明是一种证明算法行之有效的方式，它分两步：基线 条件和归纳条件。
#快速排序 def quicksrt(arr): if len(arr)<2: return arr else: pio=arr[0] less=[i for i in arr[1:] if i<pio] than=[i for i in arr[1:] if i>=pio] return quicksrt(less)+[pio]+quicksrt(than) print(quicksrt([4,5,7,2,3,9,4,0])) 运行结果： [0, 2, 3, 4, 4, 5, 7, 9]
快速排序的最糟情况运行时间为O（n**2），与选择排序一样慢，但是他的平均排序时间为O（n*log n）。而合并排序总是O（n*log n）。但是这不是绝对的，合并排序的常量总是大于快速排序，所以一般情况下认为快速排序更快。
平均情况与最糟情况假设要为从小到大的多个数排序，最糟情况就是每次都选第一个值作为基准值，这样每次操作时间都是O（n），共操作O（n）次，该算法的运行时间为O(n) * O(n) = O(n**2 )。而最佳情况每次都能选择最中间的数来排，就好像二分法一样层数为O(log n)（用技术术语说，调用栈的高度为O(log n)），而每层需要的时间为O(n)。因此整个算法需要的时间为O(n) * O(log n) = O(n log n)。
散列表 散列函数散列函数“将输入映射到数字”。这个用python字典比较好理解，每次给定key都得到的是同一个数字，每个key都对应一个value。
散列函数总是将同样的输入映射到相同的索引。
散列函数将不同的输入映射到不同的索引。
散列函数知道数组有多大，只返回有效的索引。
说到字典你可能根本不需要自己去实现散列表，任一优秀的语言都提供了散列表实现。Python提供的散列表实现就是字典，你可使用函数dict来创建散列表。
这样散列表的概念就非常好理解了，散列表通常用于查找，在网站投票中还可以过滤掉已经投过票的人，也就是去重，还有就是对于一些经常访问的网站进行缓存也使用了散列表。缓存是一种常用的加速方式，所有大型网站都使用缓存，而缓存的数据则存储在散列表中。
冲突间接描述了散列表的性能，冲突就是：给两 个键分配的位置相同。处理冲突的方式 很多，最简单的办法如下：如果两个键映射到了同一个位置，就在这个位置存储一个链表。如果一个散列表所有的值都放在第一个内存中呢，那和一个链表又有什么区别呢？最理想的情况是， 散列函数将键均匀地映射到散列表的不同位置。如果散列表存储的链表很长，散列表的速度将急剧下降。
性能在平均情况下，散列表执行各种操作的时间都为O(1)。我们来将 散列表同数组和链表比较一下。
