为什么从5000个数中找出10个最大的堆排序最快?

jcreatorqijiashe 2008-09-16 03:11:57

csdn有篇帖子是说"从5000个数中找出10个最大的用哪种排序最快",答案是堆排序. 我开始认为是选择排序,因为从第一次需要比较 5000次,第二次比较4999次... 用选择排序需要比较 5000+4999+4998+.....这么多次, 就是每次都把剩下没有比较的数字进行一次一次比较得到前10个最大的,难道用堆比较就不用一个一个比较数字吗? 用堆比较首先要建立这个堆,是个很麻烦的过程,是不是建立这个堆的过程就把前 10个最大的数字找出来了?

我看网上说:"直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作.堆排序可通过树形结构保存部分比较结果，可减少比较次数。".

他这段话不理解的是:"堆排序可通过树形结构保存部分比较结果"? 下次找最大的就不用比较这些了?

具体是为什么啊? 时间复杂度是多少?请帮忙分析一下为什么这种情况下堆排序比其他排序快

...全文

1087 10 打赏收藏转发到动态举报

写回复

用AI写文章

10 条回复

切换为时间正序

请发表友善的回复…

发表回复

Silitex 2008-09-17

打赏
举报

呵,堆在处理这些东西是最快的.!

boxer_tony 2008-09-16

打赏
举报

用快速排序的划分方法去做可能更快些接近O(n)

oo 2008-09-16

打赏
举报

最差是o(m*lgn) m=5000,n=10
选择的话是o（m*n）

jcreatorqijiashe 2008-09-16

打赏
举报

[Quote=引用 6 楼 oo 的回复:]
就是先取10个数，建一个堆，然后读后面的5000-10个数；每读一个数，跟堆里最小的数比较，如果比堆里最小的还小，就接着读；如果更大，则删除堆里最小的数，把新的数插入堆中，再接着读下一个数。直到所有数读完。
[/Quote]

这样作的时间复杂度是多少? 为了达到同样的目的,如果用选择排序的时间复杂度是多少?可以从这个角度帮我比较一下吗,谢谢

oo 2008-09-16

打赏
举报

就是先取10个数，建一个堆，然后读后面的5000-10个数；每读一个数，跟堆里最小的数比较，如果比堆里最小的还小，就接着读；如果更大，则删除堆里最小的数，把新的数插入堆中，再接着读下一个数。直到所有数读完。

jcreatorqijiashe 2008-09-16

打赏
举报

"堆排序的含义是首先保存10个最小的结果" ?
"中间状态的这10个值是有序的，这样每次保存的都是最小的10个数据" ?
我记得堆排序首先要用这 5000个数字建立一个堆吧? 难道在建立的过程中不需要一个数字一个数字的比较吗? 那么这10个最大的数字是怎么出来的? 你说的"中间状态的这10个值是有序的" 是怎么出来的?

Silitex 2008-09-16

打赏
举报

呵，很抱歉，我看得太快了！非常抱歉！
首先你搞错了题目的意思，这个堆排序的含义是首先保存10个最小的结果，然后一次遍历即可找出最小的10个值，但是中间状态的这10个值是有序的，这样每次保存的都是最小的10个数据同时取出10个中最大的数据与下一个数据进行比较。。。这里采用堆的结构存放确实比采用其他结构存放要快。