- 论坛徽章:
- 0
|
这是我 blog 上新发的一个随笔--- 一个“学而不思则惘”的故事。
前天参加一个讨论班,报告者在讲 Quick Sort 时,精力全集中在分割算法上了。他说:“你们一定要多体会一下,这个算法是先跟这边比,再跟那边比,又跟这边比,再跟那边比,如是直到相会。不这样的话,将无法理解 Quick Sort.
对这个说法我很不同意。当然线性时间的分割算法是 Quick Sort 最出彩,最有技巧的地方,但 Quick Sort 的 big idea 并不在这里。从大方向上看,Quick Sort 都干了什么?
* 找一个枢纽元 p ,把数组分成两部分,左边的比 p 小,右边的比 p 大。
* 找一个元素 r, 把数组分成两部分,比 r 小的作为子树接在 r 的左边,比 r 大的最为子树接在树的右边。
不难看出,Quick Sort 其实在建一棵二叉排序树,这是它跟其它排序算法最不同的地方。其它几种常见的排序算法都专注于如何排出一个按序的线性序列,Quick Sort 表面上也如此,但背后却藏了一棵二叉树。这也能说明为什么原始的 Quick Sort 会有一个 O(n^2) 的最坏情形,此时对应的二叉树一定非常不平衡(比如输入是基本有序的,你却用第一个元素作为枢纽元)。
其实我们可以丢掉 Quick Sort 的分割算法,通过建立二叉排序树来得到一个理论上能与 Quick Sort 抗衡的排序算法。
* 通过插入建立一棵平衡二叉树,时间界 O(nlog n);
* 先序遍历此树,得到排好序的序列,时间界 O(n);
这样,总的时间界也是 O(nlog n)。这个算法在实践中当然不如 Quick Sort,因为 Quick Sort 的分割算法效率很高,而且最后不用去遍历一棵二叉树,但是它对于理解 Quick Sort 是有帮助的。
[ 本帖最后由 win_hate 于 2007-11-4 18:27 编辑 ] |
|