一开始马上想起来寻找第k小的数，是采用快排的partition方法。但因为题目要把k之前的数排序输出，这个方法就不是很合适，因为（随机化后：http://blog.csdn.net/liangbopirates/article/details/9377105）它最差能在O(n)找到第k小的数，那么就要最差k*O(n)。如果对前面部分排序那就是O(k*logk) + O(n)了。都不合适，看来最合适的还是使用堆，能做到O(n*logK)。
但partition方法和堆方法比较，有个好处就是inplace，不占多余内存，在海量数据处理的时候有这个好处。
下面这段代码是寻找第k小的数，其精华部分是partition方法，注意这个方法的写法，维基百科和算法导论上都是这样的，比一般的写法简洁，需要记下来。本质是分了三段，第一段小于等于pivot，第二段大于pivot，第三段是未处理的。idx一直指向第二段的第一个，或者说第一段最右边过去一个，i一直指向第二段的最右边，或是第三段的最左边。那么当a[i]<pivot的时候，就把a[i]和a[idx]交换，然后idx++，这样就继续保持了这个性质。
#include <iostream>
using namespace std; void swap(int& a, int& b)
{
int tmp = a;
a = b;
b = tmp;
} // start、end分别为数组第一个元素和最后一个元素的索引
int partition(int arr[], int start, int end)
{
int pivot = arr[end];
int idx = start;
//这个循环比一般的写法简洁高效，维基百科上和算法导论上的
for(int i = start; i < end; i++) {
if(arr[i] < pivot) {
swap(arr[i], arr[idx]);
++idx;
}
}
swap(arr[idx], arr[end]);
return idx;
} int main()
{
int n; // count
cin >> n;
int m; // index
cin >> m;
int* a = new int[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
int start = 0;
int end = n - 1;
while (true)
{
int c = partition(a, start, end);
if (c == (m-1))
{
break;
}
if (c > (m - 1))
{
end = c - 1;
}
else
{
start = c + 1;
}
}
cout << a[m-1] << endl;
delete[] a;
system("pause");
}
下面是采取堆的方式，（待续）：