Quick Sort 的一个注记

ypxing

其实堆排序等选择排序,也是利用了二叉树的
关键是怎样利用
qsort的关键就是分治与分割

原帖由 win_hate 于 2007-11-5 12:32 发表
Hoare 分割在整个算法中的地位是锦上添花还是画龙点睛？在这个问题上我们可以求同存异。

其实我想强调的是，学了一个算法，一个定理之后，应该花点时间想一想这个算法或定理是怎么得来的。满足于能把算法实现 ...

win_hate

堆排序如何使用了二叉树？

ypxing

堆排序没有利用二叉树吗?

原帖由 win_hate 于 2007-11-5 12:41 发表
堆排序如何使用了二叉树？

win_hate

我说的是二叉排序树，堆排序里的那个就叫堆

ypxing

其实也可以这样理解:
有了分治和分割
一个二叉排序树的形成就是很自然的了

可能又跑到先有鸡还是先有蛋的问题上了

原帖由 win_hate 于 2007-11-5 12:44 发表
我说的是二叉排序树，堆排序里的那个就叫堆

win_hate

分治是个很大很抽象很广泛的指导思想，在涉及具体问题的时候，有时会不知道如何使用它

而建二叉排序树的想法则具体得多。

随机建一个二叉排序树的最坏时间，最好时间，平均时间刚好与 Quick Sort  的时间相应。

[ 本帖最后由 win_hate 于 2007-11-5 12:54 编辑 ]

yovn

堆排序貌似用的完全二叉树。

halve

原帖由 halve 于 2007-11-5 10:08 发表
昨天看<<啊!灵机一动>>，里头有个求最短路径的问题
用的是动态规划的方法，但最后结构上来说恰好和帕斯卡(杨辉)三角形一致
我们不能因此就说，精华在于这个帕斯卡三角形吧。。。

sorry，这里有个记忆错误 ; (
应该是求2点间的所有路径组合问题，而不是最短路径

cugb_cat

这个问题，我也是觉得快速排序的基本出发点是分而治之，至于分割方法只是其中的细节。

Sorehead

我也同意快速排序的关键在于分割，其它的只是具体的实现方法而已。