图解算法(四)
进入图解算法四，看完这一章对一些概念性的东西有了一些理解,在这里记录下。 分而治之----一种著名的递归式问题解决的方法:
D&C的思想就是不断将问题缩小规模，知道符合基线条件(基线条件通常是数组为空或者只包含一个元素)，快速排序就是一种使用了D&C的经典例子快速排序代码如下:
def quick_sort(arr):
if len(arr) < 2:
return arr#基线条件
else:
pivot = arr[0]#基准值
less = [i for i in arr[1:] if i <= pivot]
grater = [i for i in arr[1:] if i > pivot]
return quick_sort(less) + [pivot] + quick_sort(grater)print(quick_sort([10, 5, 3, 54, 23]))
【图解算法(四)】快速排序速度很快，运行时间为O(nlog^n)，但是在最遭的情况下很慢，运行时间为 O(n^2 )。
最遭情况:一般来说会选择第一个值作为基准值，如果元素在有序的情况下，左边总会得到一个空的数组，调用的高度会达到很大，这是最遭的情况。调用的栈多,栈长为O(n)，每层需要的时间为O(n)，运行时间为
O(n) * O(n) = O(n^2)
最佳情况:如果每次选择的基准值都可以将数组分为两半，那么就不需要那么多递归调用，调用栈也就少,栈长为O(log^n), 每层需要的时间为O(n)，运行时间为 O(log^n) * O(n) = O(nlog^n)小结:
>1D&C的主要思想就是将问题逐步分解，直到问题达到基线条件结束
2实现快速排序时,基准值最好随机选择，这样出现最糟情况的概率就会极小推荐阅读
- 跌跌撞撞奔向你|跌跌撞撞奔向你 第四章（你补英语，我补物理）
- 奔向你的城市
- 四首关于旅行记忆的外文歌曲
- 画解算法（1.|画解算法：1. 两数之和）
- CET4听力微技能一
- 亲子日记第186篇，2018、7、26、星期四、晴
- Guava|Guava RateLimiter与限流算法
- 特种兵训练第四天
- 第四十三篇接纳孩子的感受
- 一个选择排序算法