算法图解笔记（三）\-\--快速排序

===============================

算法的核心思想-----分而治之（D&C）

D&C的理解过程：

找出基线条件，这种条件必须尽可能简单。
不断将问题分解，直到符合基线条件。

通过下面这道题来加深对D&C的理解:

将这块长为1680m，宽640m的地均匀的分成方块，且分出的方块尽可能的大。

按照D&C的解题步骤：

基线条件：
如果长是宽的整数倍，那么就可以正好将他们分割成等分的正方形。然后通过从大到小的顺序进行筛选优先找到的肯定是最大的正方形。

按照题目中的理解就是：只需找出1680余64之间的最大公约数即可。

递归条件：
通过欧几里得算法可以得知：‘适用于这小块地的最大方块同样也适用于整块地的最大方块’。这句话正好符合了分而治之的核心思想。

先按照最大的值来分割正方形，以640作为最大正方形得出上面这张图。可以看到最右边的方块不是正方形，所以接下来对它进行相同的算法处理。

以此类推，最终得到了这样一张图：

所以最终的结果是80*80的方块。

例题2

给定一个数字数组，以递归的方式计算出该数组的总和。
如：[2,4,6]

def sum(arr):
  if len(arr) == 0:  # 基线条件
    return 0            
return                      
arr[0] + sum(arr[1:]) #递归条件
print(sum([2,3,4,5]))

例题3

用递归的形式计算列表中包含的元素数:

def count(list): 
  if len(list) == 0:
    return 0            
  return (list[0] == list[0]) + count(list[1:])
print(count([1,5,3,5]))

例题4

用递归的形式找出列表中最大的数字

def large(list):             
    if list == []:return
    if len(list) == 1:return list[0]
    else: return max(list[0], large(list[1:]))
print(large([1,2,3,4,5]))

例题5

找出二分查找算法的基线条件和递归条件
基线条件：数组长度等于1
递归条件：二分查找的核心，去掉数组一半，对另一半进行二分查找，直到满足基线条件。

D&C算法之 — 快速排序

从数组中找到一个基准值（pivot），这个基准值可以是数组中的任何一个数值。
把小于基准值的放到一边，把大于基准值的放到另外一边。然后再对它们进行快速排序，直到满足基线条件位置。快速排序相当于是递归和二分查找的结合。
快速排序的递归条件其实就是二分查找，通过不停的分割最终合并n个数组从而形成一个排好序的新数组。

## 快速排序                 
   def quicksort(list):        
    if len(list) < 2:
      return list
    else:  pivot = list[0]
      less = [i for i in list[1:] if i <= pivot]
      greater = [i for i in list[1:] if i > pivot]
      return quicksort(less) + [pivot] + quicksort(greater)
   print(quicksort([1,3,2,6,5,9,0,7,4]))

大O表示法

二分查找
$$O(log_2 n)$$

简单查找
$$O(n)$$

选择排序
$$O(n^2)$$

快速排序
$$O(nlogn)$$
最糟糕的情况下是
$$O(n^2)$$

旅行商问题算法
$$O(n!)$$

还有一种算法是合并排序，时间复杂度稳定在
$$O(nlogn)$$

快速排序时间复杂度的由来

以数组**[1,2,3,4,5,6,7,8]**为例，我们取到的基数是4。这里的分割方式与二分查找相同，所以执行次数为logn。分割完成后对每个数组的再次遍历进行分割，也就是递归条件的时间复杂度为O(n)。所以快速排序的时间复杂度是O(n) + logn。
$$O(nlogn)$$

如果是在最糟糕的情况下，这个数组本身就是排好序的时候，那么它的时间复杂度就是
$$O(n^2)$$

快速排序与合并排序的区别

因为算法有时候会带有常量，在有常量的时候它们的运算时间就不一样了。
同样是时间复杂度为nlogn
的快速排序和合并排序，在某些情况下它们的运行时间是不一样的。因为这中间n指的是执行次数，比如双方都执行了10000次，按照时间复杂度来看的话执行时间是差不多的，但是快速排序每次执行花了1毫秒，而合并排序花了10毫秒，那10000次下来时间差距就不是一点点了。

这里做个总结：快速排序在执行过程中也很快。

同样在有常量的时候，对快速排序和合并排序的运行时间也会有影响。如果出现快速查找的常量比合并查找的常量小，那么运行时间上也是快速查找占优。

平均情况和最糟情况

最糟情况指的是：比方说在快速排序的时候，取的基准值是第一个而且是整个数组中最小的一个，整个时候数组是不会被分成两半的。如果数组中第二是值是第二小的话，也会造成这种情况。这个时候就是最糟情况。

作业

用大O法表示：

打印数组中每个元素的值：
O(n)
将数组中每个元素的值都乘以2：
O(n)
只将数组中第一个元素乘以2：
O(1)
根据数组包含的元素创建一个乘法表，如果数组为[2,3,7,8,10]。首先将每个元素都乘以2，再将每个元素都乘以3，然后将每个元素都乘以7以此类推。
$$O(n^2)$$

总结

递归的核心是D&C,基线条件一般都是空数组或者只包含一个元素的数组。
找到了基线条件后，执行递归条件让它通过递归的方式慢慢靠拢基线条件即可。
在使用快速排序的时候，为了避免最糟情况基准值最好随机的去找。
在列表数据很长的时候，简单查找和二分查找不管在任何情况下速度都没得比。

loannes's blog