原题及解答出处http://blog.csdn.net/v_JULY_v/article/details/6370650
快速排序确定枢轴量的方法，确定了第K个枢轴量，那么继续递归之前的数组区间，就可以得到一个有序的K个数
推荐 http://www.cnblogs.com/morewindows/archive/2011/08/13/2137415.html 介绍的挖坑填数的解释
如果要选择一个特定的数作为枢轴量，只要将这个数与第一个数进行交换，那么这个算法仍然适用！
<pre name="code" class="cpp">// FindK.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdio.h"
#define K 3 //前4个最小的数
int array[7] = {8,10,2,4,3,6,10};
void swap(int &a, int &b)
{
int tmp = a;
a = b;
b = tmp;
}
/*void partion(int left, int right)
{
if (left < right)
{
int mid = (left+right)/2;
int pivot = array[mid];
int i = left;
int j = right;
while(i < j)
{
while(array[i] < pivot) //当A[i] = A[j]时会出现死循环
i++;
while(array[j] > pivot)
j--;
if (i < j) //i > j说明越过了枢轴量，不用进行交换了
swap(array[i], array[j]);
}
partion(left, i-1);
if (i == K-1)
return;
partion(i+1, right);
}
}
void partion(int left, int right)
{
if (left <= right)
{
int pivot = array[(left+right) / 2];
int i = left;
int j = right;
while(i < j)
{
while(array[i] < pivot)i++;
while(array[j] > pivot)j--;
if (i < j) //i > j说明越过了枢轴量，不用进行交换了
swap(array[i], array[j]);
if(array[i] == array[j]) //完全是为了避免死循环
j--;
}
partion(left, i-1);
//if (i == K-1)
//return;
partion(i+1, right);
}
}*/
void partion(int left, int right) //填坑补数法！！
{
if (left <= right)
{
int pivot = array[left];//将第一个数存至局部枢轴量中，这样第一个数就可以空出来
int i = left;
int j = right;
while(i != j)
{
while(i < j && array[j] > pivot)j--;
if (i < j)
{
array[i] = array[j]; //用j填i的坑，j是新坑
i++;
}
while(i < j && array[i] < pivot)i++;
if (i < j)
{
array[j] = array[i]; //用i填j的坑，i是新坑
j--;
}
}
array[i] = pivot; //填i的坑
if (i == K-1)
return;
partion(left, i-1); //i的位置才是枢轴量后的位置
partion(i+1, right);
}
}
int main(int argc, char* argv[])
{
partion(0, 6);
printf("%d", array[K-1]);
return 0;
}
方法二：堆排序，出堆K次即可，其中挖坑填数法再次出现，并且要注意下降的时候，选择的是子节点中的最小值进行交换。这一点要牢记
// FindK.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdio.h"
#define K 3 //前4个最小的数
int array[8] = {0,8,10,2,3,3,6,10};
void swap(int &a, int &b)
{
int tmp = a;
a = b;
b = tmp;
}
void SiftDown(int low, int high)
{
int i = low;
int j = 2*i;
int tmp = array[i];
while(j <= high)
{
if (j < high && array[j] > array[j+1]) //选择子孩子中最小的节点
j++;
if (tmp > array[j])
{
//swap(array[i], array[j]);
array[i] = array[j]; //利用好i这个坑，可以再每次循环中减少两次赋值操作，这样j成为新坑
i = j; //因为i = j，所以最后填坑的时候要填array[i]
j = i * 2;
}
else
break;
}
array[i] = tmp;
}
void HeapSort(int n)
{
int i;
for (i = n/2; i >= 1; i--)
SiftDown(i, n);
for (i = n; i > n - K; i--)
{
printf("%d", array[1]);
swap(array[1], array[i]);
SiftDown(1, i-1);
}
}
int main(int argc, char* argv[])
{
HeapSort(7);
return 0;
}