《算法图解》第四章快速排序

1.先介绍了快速排序的思想：分而治之DC（divede and conquer）

2.引入例子加强理解

def quicksort(arr):

     if len(arr)<2:基线条件

        return arr

     else:

        pivot = arr[0]

        less=[i for i in range[1:] ifarr[i]   i  <pivot]

        gretaer = [i for i in range [1:] ifarr[i]   i >pivot]

     return quicksort(less)+[pivot]+quciksort(greater)  递归条件

3.各种算法的大O

4.平均情况和最佳情况

常量：。。。。时间，对二分法和简单排序法影响不大

快速排序依赖于我们选择的基准，不管序列是不是有序的，都继续进行分组，找基准值，判断大小，如果是以开头第一个元素为基准，可能你的栈占用非常大

快速排序的最佳情况是O（log n）层*O（n）判断n次=O（nlogn）

最差情况是O（n）*O（n）=O（n^2）

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