(n lgn) time in the comparison model, even on average (see Problem 8-1), and thus the method of sorting and indexing presented in the introduction to this chapter is asymptotically inefficient.（所以，本节中的选择算法之所以具有线性运行时间，是因为这些算法没有进行排序；线性时间的结论并不需要在输入上所任何假设，即可得到。…..）
ok，综述全文，根据选取不同的元素作为主元（或枢纽）的情况，可简单总结如下：1、RANDOMIZED-SELECT，以序列中随机选取一个元素作为主元，可达到线性期望时间O（N）的复杂度。 这个在本文第一节有关编程之美第2.5节关于寻找最大的k个元素（但其n*logk的复杂度是严重错误的，待勘误,应以算法导论上的为准，随机选取主元，可达线性期望时间的复杂度），及本文第二节中涉及到的算法导论上第九章第9.2节中（以线性期望时间做选择），都是以随机选取数组中任一元素作为枢纽元的。
2、SELECT，快速选择算法，以序列中“五分化中项的中项”，或“中位数的中位数”作为主元（枢纽元），则不容置疑的可保证在最坏情况下亦为O（N）的复杂度。 这个在本文第四节末，及本文第七节，本文文末中都有所阐述，具体涉及到了算法导论一书中第九章第9.3节的最快情况线性时间的选择，及Mark Allen Weiss所著的数据结构与算法分析–c语言描述一书的第10章第10.2.3节（选择问题）中，都有所阐述。
本文结论：至此，可以毫无保留的确定此问题之结论：运用类似快速排序的partition的快速选择SELECT算法寻找最小的k个元素能做到O（N）的复杂度。RANDOMIZED-SELECT可能会有O（N^2）的最坏的时间复杂度，但上面的SELECT算法，采用如上所述的“中位数的中位数”的取元方法，则可保证此快速选择算法在最坏情况下是线性时间O（N）的复杂度。
最终验证：
1、我想，我想，是的，仅仅是我猜想，你可能会有这样的疑问：经过上文大量严谨的论证之后，利用SELECT算法，以序列中“五分化中项的中项”，或“中位数的中位数”作为主元（枢纽元），的的确确在最坏情况下O（N）的时间复杂度内找到第k小的元素，但是，但是，咱们的要面对的问题是什么?咱们是要找最小的k个数阿！不是找第k小的元素，而是找最小的k个数（即不是要你找1个数，而是要你找k个数）?哈哈，问题提的非常之好阿。
2、事实上，在最坏情况下，能在O（N）的时间复杂度内找到第k小的元素，那么，亦能保证最坏情况下在O（N）的时间复杂度内找到前最小的k个数，咱们得找到一个理论依据，即一个证明（我想，等你看到找到前k个数的时间复杂度与找第k小的元素，最坏情况下，同样是O（N）的时间复杂度后，你便会100%的相信本文的结论了，然后可以通告全世界，你找到了这个世界上最靠谱的中文算法blog，ok，这是后话）。
算法导论第9章第9.3节练习里，有2个题目，与我们将要做的证明是一个道理，请看：
Exercises 9.3-4: Suppose that an algorithm uses only comparisons to find the ith smallest element in a set of n elements. Show that it can also find the i – 1 smaller elements and the n – i larger elements without performing any additional comparisons.（假设对一个含有n个元素的集合，某算法只需比较来确定第i小的元素。证明：无需另外的比较操作，它也能找到比i 小的i-1个元素和比i大的n-i个元素）。
Exercises 9.3-7 Describe an O(n)-time algorithm that, given a set S of n distinct numbers and a positive integer k ≤ n, determines the k numbers in S that are closest to the median of S.（给出一个O（N）时间的算法，在给定一个有n个不同数字的集合S以及一个正整数K<=n后，它能确定出S中最接近其中位数的k个数。）
怎么样，能证明么?既然通过本文，咱们已经证明了上述的SELECT算法在最坏情况下O（N）的时间内找到第k小的元素，那么距离咱们确切的问题：寻找最小的k个数的证明，只差一步之遥了。
给点提示：
1、找到了第K小的数Xk 为O(n)，再遍历一次数组，找出所有比k小的元素O（N）（比较Xk与数组中各数的大小，凡是比Xk小的元素，都是我们要找的元素），最终时间复杂度即为： O（N）（找到第k小的元素） + 遍历整个数组O（N）=O（N）。这个结论非常之简单，也无需证明（但是，正如上面的算法导论练习题9.3-7所述，能否在找到第k小的元素后，能否不需要再比较元素列?）。
2、我们的问题是，找到 第k小的元素后Xk，是否Xk之前的元素就是我们 要找的最小 的k个数，即，Xk前面的数，，是否都<=Xk?因为 那样的话，复杂度则 变为：O（N）+O（K）（遍历找到的第k小元素 前面的k个元素）=O（N+K）=O（N），最坏情况下，亦是线性时间。
终极结论：证明只有一句话：因为本文我们所有的讨论都是基于快速排序的partition方法，而这个方法，每次划分之后，都保证了 枢纽元Xk的前边元素统统小于Xk，后边元素统统大于Xk（当然，如果你是属于那种打破沙锅问到底的人，你可能还想要我证明partition过程中枢纽元素为何能把整个序列分成左小右大两个部分。但这个不属于本文讨论范畴。读者可参考算法导论第7章第7.1节关于partition过程中循环不变式的证明）。所以，正如本文第一节思路5所述在0（n）的时间内找到第k小的元素，然后遍历输出前面的k个小的元素。如此，再次验证了咱们之前得到的结论：运用类似快速排序的partition的快速选择SELECT算法寻找最小的k个元素，在最坏情况下亦能做到O（N）的复杂度。
5、RANDOMIZED-SELECT，每次都是随机选取数列中的一个元素作为主元，在0（n）的时间内找到第k小的元素，然后遍历输出前面的k个小的元素。 如果能的话，那么总的时间复杂度为线性期望时间：O（n+k）=O（n）（当k比较小时）。
所以列，所以，恭喜你，你找到了这个世界上最靠谱的中文算法blog。
updated：
，再回头，便生出无限羁绊。那是彼此的刺在对方心里留下的痕迹，
