程序员编程艺术：第三章、寻找最小的k个数
作者：July。
时间：二零一一年四月二十八日。
致谢：litaoye， strugglever，yansha，luuillu，Sorehead，及狂想曲创作组。
微博：http://weibo.com/julyweibo。
出处：http://blog.csdn.net/v_JULY_v。
----------------------------------
前奏
@July_____：1、当年明月：“我写文章有个习惯，由于早年读了太多学究书，所以很痛恨那些故作高深的文章，其实历史本身很精彩，所有的历史都可以写得很好看，...。”2、IT技术文章，亦是如此，可以写得很通俗，很有趣，而非故作高深。希望，我可以做到。
下面，我试图用最清晰易懂，最易令人理解的思维或方式阐述有关寻找最小的k个数这个问题（这几天一直在想，除了计数排序外，这题到底还有没有其它的O（n）的算法? ）。希望，有任何问题，欢迎不吝指正。谢谢。
寻找最小的k个数
题目描述：5.查找最小的k个元素
题目：输入n个整数，输出其中最小的k个。
例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。
第一节、各种思路，各种选择
0、 咱们先简单的理解，要求一个序列中最小的k个数，按照惯有的思维方式，很简单，先对这个序列从小到大排序，然后输出前面的最小的k个数即可。
1、 至于选取什么的排序方法，我想你可能会第一时间想到快速排序，我们知道，快速排序平均所费时间为n*logn，然后再遍历序列中前k个元素输出，即可，总的时间复杂度为O（n*logn+k）=O（n*logn）。
2、 咱们再进一步想想，题目并没有要求要查找的k个数，甚至后n-k个数是有序的，既然如此，咱们又何必对所有的n个数都进行排序列?
这时，咱们想到了用选择或交换排序，即遍历n个数，先把最先遍历到得k个数存入大小为k的数组之中，对这k个数，利用选择或交换排序，找到k个数中的最大数kmax（kmax设为k个元素的数组中最大元素），用时O（k）（你应该知道，插入或选择排序查找操作需要O（k）的时间），后再继续遍历后n-k个数，x与kmax比较：如果x<kmax，则x代替kmax，并再次重新找出k个元素的数组中最大元素kmax‘（多谢kk791159796 提醒修正）；如果x>kmax，则不更新数组。这样，每次更新或不更新数组的所用的时间为O（k）或O（0），整趟下来，总的时间复杂度平均下来为：n*O（k）=O（n*k）。
3、 当然，更好的办法是维护k个元素的最大堆，原理与上述第2个方案一致，即用容量为k的最大堆存储最先遍历到的k个数，并假设它们即是最小的k个数，建堆费时O（k）后，有k1<k2<...<kmax（kmax设为大顶堆中最大元素）。继续遍历数列，每次遍历一个元素x，与堆顶元素比较，x<kmax，更新堆（用时logk），否则不更新堆。这样下来，总费时O（k+（n-k）*logk）=O（n*logk）。此方法得益于在堆中，查找等各项操作时间复杂度均为logk（不然，就如上述思路2所述：直接用数组也可以找出前k个小的元素，用时O（n*k））。
4、 按编程之美第141页上解法二的所述，类似快速排序的划分方法，N个数存储在数组S中，再从数组中随机选取一个数X（随机选取枢纽元，可做到线性期望时间O（N）的复杂度，在第二节论述），把数组划分为Sa和Sb俩部分，Sa<=X<=Sb，如果要查找的k个元素小于Sa的元素个数，则返回Sa中较小的k个元素，否则返回Sa中k个小的元素+Sb中小的k-|Sa|个元素。像上述过程一样，这个运用类似快速排序的partition的快速选择SELECT算法寻找最小的k个元素，在最坏情况下亦能做到O（N）的复杂度。不过值得一提的是，这个快速选择SELECT算法是选取数组中“中位数的中位数”作为枢纽元，而非随机选取枢纽元。
5、 RANDOMIZED-SELECT，每次都是随机选取数列中的一个元素作为主元，在0（n）的时间内找到第k小的元素，然后遍历输出前面的k个小的元素。 如果能的话，那么总的时间复杂度为线性期望时间：O（n+k）=O（n）（当k比较小时）。
Ok，稍后第二节中，我会具体给出RANDOMIZED-SELECT(A, p, r, i)的整体完整伪码。在此之前，要明确一个问题：我们通常所熟知的快速排序是以固定的第一个或最后一个元素作为主元，每次递归划分都是不均等的，最后的平均时间复杂度为：O（n*logn）,但RANDOMIZED-SELECT与普通的快速排序不同的是，每次递归都是随机选择序列从第一个到最后一个元素中任一一个作为主元。
6、 线性时间的排序，即计数排序，时间复杂度虽能达到O（n），但限制条件太多，不常用。
7、 updated： huaye502在本文的评论下指出：“可以用最小堆初始化数组，然后取这个优先队列前k个值。复杂度O(n)+k*O(log n)”。huaye502的意思是针对整个数组序列建最小堆，建堆所用时间为O（n）（算法导论一书上第6章第6.3节已经论证，在线性时间内，能将一个无序的数组建成一个最小堆），然后取堆中的前k个数，总的时间复杂度即为：O（n+k*logn）。
关于上述第7点思路的继续阐述：至于思路7的O（n+k*logn）是否小于上述思路3的O（n*logk），即O（n+k*logn）?< O（n*logk）。粗略数学证明可参看如下第一幅图，我们可以这么解决：当k是常数，n趋向于无穷大时，求（n*logk）/（n+k*logn）的极限T，如果T>1，那么可得O（n*logk）>O（n+k*logn），也就是O（n+k*logn）< O（n*logk）。虽然这有违我们惯常的思维，然事实最终证明的确如此，这个极值T=logk>1，即采取建立n个元素的最小堆后取其前k个数的方法的复杂度小于采取常规的建立k个元素最大堆后通过比较寻找最小的k个数的方法的复杂度。但，最重要的是，如果建立n个元素的最小堆的话，那么其空间复杂度势必为O（N），而建立k个元素的最大堆的空间复杂度为O（k）。所以，综合考虑，我们一般还是选择用建立k个元素的最大堆的方法解决此类寻找最小的k个数的问题。
也可以如gbb21所述粗略证明：要证原式k+n*logk-n-k*logn>0，等价于证（logk-1）n-k*logn+k>0。当when n -> +/inf（n趋向于正无穷大）时，logk-1-0-0>0，即只要满足logk-1>0即可。原式得证。即O（k+n*logk）>O（n+k*logn） =>O（n+k*logn）< O（n*logk），与上面得到的结论一致。
事实上，是建立最大堆还是建立最小堆，其实际的程序运行时间相差并不大，运行时间都在一个数量级上。因为后续，我们还专门写了个程序进行测试，即针对1000w的数据寻找其中最小的k个数的问题，采取两种实现，一是采取常规的建立k个元素最大堆后通过比较寻找最小的k个数的方案，一是采取建立n个元素的最小堆，然后取其前k个数的方法，发现两相比较，运行时间实际上相差无几。结果可看下面的第二幅图。
