===========================================================
第K小数的新算法
===========================================================
作者: fesir(http://fesir.itpub.net)
发表于: 2006.05.17 20:42
分类: C/C++
出处: http://fesir.itpub.net/post/4728/96170
---------------------------------------------------------------
发表于: 2006.05.17 20:42
分类: C/C++
出处: http://fesir.itpub.net/post/4728/96170
---------------------------------------------------------------
http://toocn.blogchina.com/4889853.html
在一个数组中，找出第K小的数。
这是我在以前别人的BLOG里面看到的一个题目，几乎所有的人都用快速排序的思想来做的。
还是找个中间点，如果中间点的位置为K，那么它就是那个元素，否则如果>K,就在左边继续用PARTITION的算法，如果
这个和PAR方法的思想一致。
下面是我今天上自习的时候想到的一种方法。
我用下面的思想来做这个问题：
首先我们先对数组的前K个数进行堆排序【K个数的最大堆】，然后对剩下的N-K的数字，依次加入堆，并将最大值退出堆。
最后的堆顶元素就是第K小的数字。
代码就不写了，分析一下复杂度，O(n)建堆log(k),然后的插入堆的比较次数最多是(n-k)log(k),
所以它的复杂度比较平均，在极端情况下它的效率也是很高的。
这里有个人写的代码，用上面第一种方法得到的
re: 锟斤拷K小锟斤拷锟斤拷锟斤拷锟姐法 
