免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
123下一页
最近访问板块 发新帖
查看: 11454 | 回复: 22

[算法] Quick Sort 的一个注记 [复制链接]

论坛徽章:
0
发表于 2007-11-04 18:21 |显示全部楼层
这是我 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 编辑 ]

论坛徽章:
0
发表于 2007-11-04 19:36 |显示全部楼层
看了版主的讲解,我想到一道关于quick sort的题:
"通常快速排序为了效率,都是选取中间点作为枢纽元. 现有从1到15,15个元素.请问这15个元素如何排列,能让选取中点作为枢纽元的排序方案也只能有O(n^2)的效率?"

论坛徽章:
0
发表于 2007-11-04 22:21 |显示全部楼层
多谢! 豁然开朗

论坛徽章:
1
荣誉版主
日期:2011-11-23 16:44:17
发表于 2007-11-04 23:29 |显示全部楼层
好久不见老大,学习。

论坛徽章:
0
发表于 2007-11-04 23:45 |显示全部楼层
呵呵,我更倾向于“Quick Sort的精华在于分割“。

论坛徽章:
0
发表于 2007-11-05 00:33 |显示全部楼层
多谢各位新老朋友捧场

论坛徽章:
0
发表于 2007-11-05 00:45 |显示全部楼层
原帖由 yovn 于 2007-11-4 23:45 发表
呵呵,我更倾向于“Quick Sort的精华在于分割“。


Hoare 的分割方法确实巧妙。不过从理论上看,这个分割方法是相对次要的。只要分割是 O(n)  的,就能保证整个算法的平均时间为 O(nlog n)。设计一个 O(n) 的分割算法,不需要太多智慧,比如随便取一个枢纽元,然后与余下的数逐个比较,分别放到一个临时数组的两头,最后再复制回去---愚笨如此,仍是 O(n) 的。

Hoare 分割的贡献主要有两个:

1、可以就地(in-place)排序
2、效率高,可以打败其它 O(nlog n) 算法。

但 Quick Sort 背后的二叉树使得 Quick Sort 成为一个 O(nlog n) 的算法。如果抛弃就地排序的要求,Hoare 分割在我看来只是一个实现细节。

论坛徽章:
0
发表于 2007-11-05 08:35 |显示全部楼层
个人认为精华在于:
找一个元素,然后进行分割,分治

原帖由 win_hate 于 2007-11-5 00:45 发表


Hoare 的分割方法确实巧妙。不过从理论上看,这个分割方法是相对次要的。只要分割是 O(n)  的,就能保证整个算法的平均时间为 O(nlog n)。设计一个 O(n) 的分割算法,不需要太多智慧,比如随便取一个枢纽元 ...

论坛徽章:
0
发表于 2007-11-05 10:08 |显示全部楼层
原帖由 win_hate 于 2007-11-5 00:45 发表


Hoare 的分割方法确实巧妙。不过从理论上看,这个分割方法是相对次要的。只要分割是 O(n)  的,就能保证整个算法的平均时间为 O(nlog n)。设计一个 O(n) 的分割算法,不需要太多智慧,比如随便取一个枢纽元 ...

个人意见,精华在于分割
几种高效的排序算法如归并排序,快速排序都是这一思想的体现
只不过快排恰好在结构上与二叉树一致
昨天看<<啊!灵机一动>>,里头有个求最短路径的问题
用的是动态规划的方法,但最后结构上来说恰好和帕斯卡(杨辉)三角形一致
我们不能因此就说,精华在于这个帕斯卡三角形吧。。。

btw: 这个也是看问题角度不同的原因
可能 win_hate 看重的是二叉树这一结构在计算机中的广泛应用,而持有异议的人更注重分而治之的思路

[ 本帖最后由 halve 于 2007-11-5 10:43 编辑 ]

论坛徽章:
0
发表于 2007-11-05 12:32 |显示全部楼层
Hoare 分割在整个算法中的地位是锦上添花还是画龙点睛?在这个问题上我们可以求同存异。

其实我想强调的是,学了一个算法,一个定理之后,应该花点时间想一想这个算法或定理是怎么得来的---即使这个问题可能没有答案,但仍是有益的。满足于能把算法实现或能把定理记住,都是不够的。


但我不能同意这位朋友的观点:

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

用二叉树来排序,是个很自然,很聪明的想法;但用帕斯卡三角形来爬楼梯---则是一个很疯狂,很愚笨的想法。

[ 本帖最后由 win_hate 于 2007-11-5 12:36 编辑 ]
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP