美文网首页
算法图解 (四)

算法图解 (四)

作者: EruDev | 来源:发表于2018-05-29 18:22 被阅读0次

第四章 快速排序

分而治之

这个概念是书中一直提到的, 个人理解就是把问题分解出来, 抽出来一小块一小块解决

递归

第三章就讲到递归了, 两个关键点找出基线条件和递归条件

记得之前写过一个妹纸图爬虫, 主要就是用的递归调取本身, 来爬取下一页的图片。 整个站都可以爬下来, 前提是网站反爬不厉害...

快速排序

简称快排, 一种排序算法。 在平均情况下, 排序 n 个项目要 O(nlogn)。 最坏的情况下则需要 O(n2)。 事实上,快速排序 O(nlogn) 通常明显比其他算法更快, 因为它的内部循环(inner loop)可以在大部分的架构上很有效率地达成

代码:

# coding: utf-8

"""
快速排序
"""

def quick_sort(arr):
    if len(arr) < 2:
        return arr
    else:
        temp = arr[0]
        less = [i for i in arr[1:] if i < temp]
        greater = [i for i in arr[1:] if i > temp]

        return quick_sort(less) + [temp]+ quick_sort(greater)

arr = [32, 4, 54, 65, 5, 864]
print(quick_sort(arr))

小结

  • 分而治之将问题逐步分解. 使用分而治之处理列表的时候, 基线条件可能是空数组或只包含一个元素的数组
  • 实现快速排序, 请随机的选择用作基准值的元素。 快速排序的平均运行时间 O(nlogn)

相关文章

  • 算法图解 (四)

    第四章 快速排序 分而治之 这个概念是书中一直提到的, 个人理解就是把问题分解出来, 抽出来一小块一小块解决 递归...

  • 图解算法(四)

    进入图解算法四,看完这一章对一些概念性的东西有了一些理解,在这里记录下。 分而治之----一种著名的递归式问题解决...

  • 《算法图解》note 11 总结

    这是《算法图解》的第十一篇读书笔记,是一篇总结。经过1个月的时间,终于把《算法图解》看完了。个人认为,《算法图解》...

  • 算法图解四(快速排序)

    给大家分享快速排序之前,讲一下D&C算法。(分而治之算法) EX: 将一块长方形的土地,分成最多正方形,且不浪费,...

  • 算法图解读书笔记

    date: 2017-9-16 11:11:15title: 算法图解读书笔记 算法图解: http://www....

  • 算法图解 读书笔记

    date: 2017-9-16 11:11:15title: 算法图解读书笔记 算法图解: http://www....

  • 算法学习工具

    算法图解可视化工具

  • 图解LZ77压缩算法

    图解LZ77压缩算法

  • 前端

    买一本算法书看一下算法图解

  • 归并排序

    图解排序算法(四)之归并排序 基本思想 归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用...

网友评论

      本文标题:算法图解 (四)

      本文链接:https://www.haomeiwen.com/subject/yxwajftx.html