求前k小的数，一般人的想法就是先排序，然后再遍历，但是题目只是求前N小，没有必要完全排序，所以可以想到部分排序，而能够部分排序的排序算法我能想到的就是堆排序和快排了。

第一种思路，局部堆排序。

首先，建立一个大小为N的大顶堆，时间复杂度klgk，然后用其余的数和堆顶元素比较，如果小于堆顶元素则与堆顶元素交换，并进行一次调整，时间复杂度(n-k)lgk，然后klgk可以常数级，(n-k)lgk=O(n)。

第二种思路，利用快排的partition。

只需要稍微修改qsort函数即可，增加判断条件，当partition小于k则快排partition+1到right，如果partition大于k则快排left到partition-1，如果partition等于k，则直接输出数组前k个数，即所求。因为每一轮partition，左部的数都会小于基准数，右部大于基准数 ，所以如果基准下标小于k，说明第k大的数肯定不在基准左部，所以可以缩小搜索条件，直接搜索基准右部，同理基准下标大于k，说明第k大的数肯定不在基准右部，直接搜索基准左部。不过需要注意的一点是qsort中的if(left<right)要改成if(left<right)，因为判断partition==k要在下一个递归中。时间复杂度网上证明是O(n)。