当年学数据结构的时候没学明白,怎么比着比着就排好队了?
想象需要对一堆人的年龄排序,让大家先排成一列,然后找一个基准,小的站左边,大的站右边,变成两列,然后这两列的每列再这么搞,最后结果就是变成一排,最小的在左边,最大的在右边。
有一堆苹果,你随便拿了一个,然后碰到比他小的就放左边,比他大的就放右边,然后两堆在分别递归这么干,直到每队只有一个。
每次分成两堆,下次迭代只需要在每堆内进行比较,这样重复比较的次数就少了很多。快排从发明算法到一个完全正确的程序,经历了十几年。
分而治之。 快排的核心在于证明时间复杂度。
@wuBing 一个动态展示排序过程的SWF,希望对你有用,具体:下载链接中的gif到本地,并改扩展名为.swf