算法图解四(快速排序)

作者: Ron_罗恩 | 来源:发表于2019-10-25 23:10 被阅读0次

    给大家分享快速排序之前,讲一下D&C算法。(分而治之算法)

    EX:

    将一块长方形的土地,分成最多正方形,且不浪费,怎么做?

    这时候就要用到D&C算法。将长方形的宽,作为最大的正方形的边。首先切除一个正方形。再从剩下的长方形中再切出一个(以长方形宽为边的正方形)。用这个方法直到找出最小的一个正方形。大功告成!

    图片来自《算法图解》 图片来自《算法图解》 图片来自《算法图解》 图片来自《算法图解》

    EX:

    用递归算法求一个列表中所有数字之和?下列Code 使用D&C算法

    (1)找出简单的基准条件。

    (2)缩小问题的规模,使其符合基准条件。


    快速排序就是建立D&C算法的基础之上的算法。

    (1)选出基准值。

    (2)将数组分成两个子数组。小于基准值的元素和大于基准值的元素。

    (3)对这个两个子数组进行快速排序。

    算法时间:

    二分查找O(logn)<快速排序O(nlogn)<选择排序O(n*2)

    PS:

    如果你阅读之后,有所收获。请记得点赞哦。o(* ̄︶ ̄*)o。你的支持将是我写作的动力。

    相关文章

      网友评论

        本文标题:算法图解四(快速排序)

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