感觉这是个经典问题了，但是今天看维基百科的时候还是有了新的发现，话说这个问题，比较挫的解决方案有先排序，然后找到第K小的，复杂度是O(nlogn)，还有就是利用选择排序或者是堆排序来搞，选择排序是O(kn)，堆排序是O(nlogk)，比较好的解决方案是利用类似快速排序的思想来找到第K小，复杂度为O(n)，但是最坏情况可能达到O(n^2)，不过今天要说的，就是还有种方法可以使得最坏情况也是O(n)。

    日本程序员norahiko，写了一个排序算法的动画演示，非常有趣。这个周末，我就用它当做教材，好好学习了一下各种排序算法。 排序算法(Sorting algorithm)是计算机科学最古老、最基本的课题之一。要想成为合格的程序员，就必须理解和掌握各种排序算法。 目前，最常见的排序算法大概有七八种，其中"快速排序"(Quicksort)使用得最广泛，速度也较快。它是图灵奖得主C. A. R. Hoare(1934--)于1960时提出来的。 "快速排序"的思想很...