当前位置： 查字典图书网> 编程> 数据结构与算法分析> 叹为观止的算法基础经典

叹为观止的算法基础经典

hubugui 对 数据结构与算法分析 的书评 发表时间：2006-12-26 16:12:40

开篇第一章引论的第一节提出一个问题：

“设有一组N个数而要确定其中第K个最大者”

并给出两种解法

        全排序后返回K位置上的元素。平均复杂度O(NLogN)

        再建立一个临时数组，从N中读取K个数，全排序，然后依次读入其余N - K个数进来和第K名比较，大于K的值则插入到合适位置，只待循环完毕返回K位置元素。平均复杂度O(KLogK + (N - K))

这两种方法在N=100万，K=50万时速度都尤其“漫长“，往往让人抓耳挠腮，作者讲叙到还有一种算法1秒钟就可以得出答案。该算法原理和快速排序一致，但只有一个方向的递归。平均复杂度O(N)。

先选取一个中值元素（该中值是否合理将影响到算法效率），然后将大于等于该数的元素放到其左侧，小于该数的放到右侧，如7 4 6 8 0 -1 选取6作为中值元素，则结果应该为4 0 -1 6 8 7，接下来比较K值和现在的中值元素6所在索引(3)，如何小于3，则只需在索引0~2间再进行递归操作继续选取第K名，大于3则在4~5中递归选取第K - 3名即可。还有一关键是该为递归中的数组长度选取一临界点，小于该临界则进行选择排序，插入排序即可，比如20以内。

算法真是精妙，赶紧学习。

有用 16 无用 4

您对该书评有什么想说的？

对“叹为观止的算法基础经典”的回应

新世纪的神
新世纪的神 2016-04-13 12:02:35

其实这就是快排的思想，好多算法书里都有这个例子

回应他
Bono
Bono 2016-02-23 12:12:39

这不就是快排嘛

回应他
菜芽虎虎
菜芽虎虎 2015-08-21 19:32:54

尼玛翻译的好烂啊，你们真的看下去了？

回应他
[已注销]
[已注销] 2013-06-15 02:59:16

作者的说的是用简单的算法排序排序，例如冒泡法，所以复杂度是O(N^2)。如果用O(nlogn)的排序算法，在N=1000000的时候和O(N)的算法差距是大约20倍，体现不出优越性来。

第二种算法也没有O(klogk+N-k)那么快的。第二阶段如果排序好的序列用数组实现，那么最坏情况是(N-k)(logk + k) (二分法查找插入位置，每次都插入在最前，一共N-k次)，如果用链表实现，那么最坏情况是(N-k)(k+C)。然后再加上排序的O(k^2)。

回应他
Marvin
Marvin 2010-07-28 16:26:06

不就是快排吗···你可以再试试归并排序和这个原理差不多···

回应他
GORILLAZ
GORILLAZ 2009-10-21 12:28:54

到 其实就是快排的第一步啊，很多书上都有讲

回应他
吴志敏
吴志敏 2009-09-10 08:12:24

第二个算法果然高超！
www.h2w1.com/i/kauu

回应他
adam.lu
adam.lu 2009-08-24 11:37:45

好难

回应他
river4321
river4321 2009-07-20 16:42:44

作者的个人主页上就有源代码，课后题答案csdn也下的到。

回应他
SilverWing
SilverWing 2009-05-20 17:13:44

听起来不错！这可是面试时经常会被问到的题目啊

回应他
已注销
已注销 2009-02-26 22:41:53

mark！

回应他
netbeanstang
netbeanstang 2009-02-22 17:22:33

才看了开头就 叹为观止？ 看完再说吧。

回应他
hubugui
hubugui 2007-07-30 11:20:47

俺也没有呢 也许找不着更好咯 自己一点点地敲 理解更深

回应他
破晓
破晓 2007-07-04 21:55:51

本书的代码，你有吗？
到官网上找不到啊！

回应他

《数据结构与算法分析》热门书评

数据结构与算法分析

书名： 数据结构与算法分析
作者： [美] Mark Allen Weiss
出版社： 机械工业出版社
原作名： Data Structures and Algorithm Analysis in C:Second Edition
副标题： C语言描述
译者： 冯舜玺
出版年： 2004-1-1
页数： 391
定价： 35.00元
装帧： 平装
丛书： 计算机科学丛书
ISBN： 9787111127482