快速排序
通过不断比较和移动交换实现冒泡排序的升级。
基本思想:分治法
通过一趟排序将一系列数据分割成独立的两部分,其中的一部分数据均小于另一部分数据。
然后分别对这两部分数据继续通过分割进行排序,直到每个子序列只有一个元素或者为空,最后使整个序列变得有序。
分治法简述
一. 分解;
将一个规模比较大的问题,通过分解,变为若干个规模比较小的相同子问题。
(该相同子问题之间必须相互独立,通过合并子问题的解,可以得到原问题的解。)
二. 治理:
子问题与原问题形式相同,当规模足够小时,可以轻松解决。
三. 合并:
将子问题逐层合并为原问题的解;
使用递归可以将分治问题快速解决。