程序员面试题狂想曲：寻找最小的k个数（号外

作者：July
时间：二零一一年四月二十八日
致谢：litaoye，strugglever，yansha，luuillu，Sorehead，及狂想曲创作组。
微博：http://weibo.com/julyweibo。
出处：http://blog.csdn.net/v_JULY_v。
----------------------------------

号外
我先告诉你什么叫做号外，号外的意思是：比如我现在出了第二章，在出第三章之前，特意临时写一篇文章，补充阐述相关的问题，而不列入原有的章节之中，特此称为号外。

下面，我试图用最清晰易懂，最易令人理解的思维或方式阐述有关寻找最小的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，k1<k2,K3<…<kmax（kmax设为k个元素的数组中最大元素），用时O（k），后再继续遍历后n-k个数，x与kmax比较，如果x<kmax，则x代替kmax，并再次排序k个元素的数组。如果x>kmax，则不更新数组。这样，每次更新或不更新数组的所用的时间为O（k）或O（0），整趟下来，总的时间复杂度平均下来为：n*O（k）=O（n*k）。
3、当然，更好的办法是维护k个元素的最大堆，原理与上述第3个方案一致，即用容量为k的最大堆存储最小的k个数，此时，k1<k2<...<kmax（kmax设为大顶堆中最大元素）。遍历一次数列，n，每次遍历一个元素x，与堆顶元素比较，x<kmax，更新堆（用时logk），否则不更新堆。这样下来，总费时O（n*logk）。此方法得益于在堆中，查找等各项操作时间复杂度均为logk（不然，就如上述思路2所述：直接用数组也可以找出前k个小的元素，用时O（n*k））。
4、按编程之美第141页上的所述，类似快速排序的划分方法，N个数存储在数组S中，再从数组中随机选取一个数X，把数组划分为Sa和Sb俩部分，Sa<=X<=Sb，如果要查找的k个元素小于Sa的元素个数，则返回Sa中较小的k个元素，否则返回Sa中k个小的元素+Sb中小的k-|Sa|个元素。书上提到，此题的复杂度为logk*O（n），每次操作O（n），深度为logk（但我目前手头里，暂缺一个证明），即需要logk这样的操作，所以，总的时间复杂度为：O（n*logk）。
5、随机快排，每次都是随机选取数列中的一个元素作为主元，在0（n）的时间内找到第k小的元素，然后遍历输出前面的k个小的元素。如果能的话，那么总的时间复杂度为O（n+k）=O（n）（当k比较小时）。

Ok，稍后，我会具体给出RANDOMIZED-SELECT(A, p, r, i)的整体完整伪码。在此之前，要明确一个问题，即我们通常所熟知的快速排序是以固定的最后一个元素作为主元，每次递归划分都是不均等的，最后的平均时间复杂度为：O（n*logn）,但随机快速排序与普通的快速排序不同的是，每次递归都是随机选择序列从第一个到最后一个中任一一个元素作为主元。

6、线性时间的排序，即计数排序。这个大家都很熟知，不做具体阐述。
7、updated：huaye502在本文的评论下指出：“可以用最小堆（刚开始还以为他说错了）初始化数组，然后取这个优先队列前k个值。复杂度O(n)+k*O(log n)”。ok，刚开始以为他弄错了，后经朋友litaoye提醒，是对的。huaye502的意思是针对整个数组序列建最小堆，建堆所用时间为O（n）（算法导论一书上第6章第6.3节已经论证，在线性时间内，能将一个无序的数组建成一个最小堆），然后取堆中的前k个数，总的时间复杂度即为：O（n）+k*O（logk）。
至于O（n）+k*O（logn）是否小于与上述思路四的O（n*logk），即O（n）+k*O（logn）？<O（n*logk）。我们只能这样说，视n、和k的大小情况而定。

updated：算法导论（中文第二版）上第111页关于RANDOMIZED-PARTITION(A, p, r)为O（n）的证明，看到了。但我始终不敢完全确认，找出前k个最小的数，即为O（n

补充：综合编程 , 其他综合 ,