算法学习笔记(2):快排

前言:最近两天又改变了下学习方法。直接看《算法导论》,然后看完立刻实现感觉太直接,自己不需要动脑子,引导性也不是很强。于是去hackerrank上一点点学。昨天把warmup和implement完成了,熟悉了下大概环境。今天把插排和快排看完了。

网上之前一直流传的一个图书馆大妈给书排序的段子形象的解释了快排的思路。

图书馆看见两个志愿者需要把还回来的一堆书按顺序入架, 管理员大妈给他们教的时候说:『你先在这堆书里拉出一本来,把比它号小的扔到一边,比它大的扔到另一边,然后剩下两堆继续这样整,这样排的快!』

从分治法的思维来看,快排和堆排的路数差不多。堆排中是假设左子树和右子树是已经排好了的树,而快排中则是假设左侧的序列和右侧的序列分别是排好了的序列。其实就是每次排序之前都能保证小的在左面,大的在右面。思路很简朴。

对比之下,由于堆排中使用了二叉树的结构,所以在排序这个事情上徒增了复杂度,所以导致了其比快排效率低。

过来人也都对这种『凡事不能搞得太复杂』的思想也有过阐述。

Everything should be made as simple as possible, but no simpler.

——爱因斯坦

万物之始,大道至简,衍化至繁。

——老子《道德经》

说回图书馆大妈的段子。毕竟图书馆大妈不是程序员,只能想到最简朴的快排的方法。事实上,在把书分成三摞(即『比Pivot小的一摞』、『Pivot一摞』、『比Pivot大的一摞』)的不停迭代的过程中,实际上是个把最初的一整摞书摊开的过程。形象的说就是原来一摞书撑死只占A4纸那么大的面积,然而摊开之后会占许多倍原来的面积。即段子中的排序实际上是会多占空间的。

对应的也有一种『原地快排』的算法,并不需要把书按着大小摊开,只需要把书从那一摞里『抽出来』再『塞回去』(对应着其实就是数组元素之间的互相调换)即可以完成排序。《算法导论》上杭也介绍的是这种快排方法。

这种原地快排的代码也不是很复杂,书上写的也很清晰。我觉得一个挺巧妙的地方是《算法导论》中使用两个下标来圈定了『大于Pivot的右侧子数组』。这样处理的时候很直观。

别的关于快排也并没有什么了,毕竟学的时候感觉一切都是那么顺理成章。又想起来小波课上老师说的,『一看都不对的结论肯定有问题』。