给大家分享快速排序之前,讲一下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。你的支持将是我写作的动力。
网友评论