本意是这样的，给定一个整数数组，查找最小k个元素或最大k个元素。
假定有这样一组数列{ 10, 33, 2, 4, 55, 6, 12, 34, 456, 66, 43, 23, 65, 1, 345, 61, 76, 31, 43, 76 };
如和求出最小的k个值，或最大的k个值？下面我结合快速排序来进行了查找，本人只是做了一个实例，抛砖引玉，希望大家有更好的方法，代码是用C#代码实现的。
private int Partition(int[] R, int low, int high)
{
int temp = R[low];
while (low < high)
{
while (low < high && temp <= R[high])
{
high--;
}
R[low] = R[high];
while (low < high && temp >= R[low])
{
low++;
}
R[high] = R[low];
}
R[low] = temp;
return low;
}
/// <summary>
/// 快速排序
/// </summary>
/// <param name="R"></param>
/// <param name="low"></param>
/// <param name="high"></param>
private void QuickSort(int[] R, int low, int high,int k)
{
int pivotLoc = 0;
if (low < high)
{
pivotLoc = Partition(R, low, high);
QuickSort(R, low, pivotLoc - 1, k);
if ( pivotLoc <= k)
{
QuickSort(R, pivotLoc + 1, high, k);
}
}
}
这是求k个最小值的，如果求ｋ个最大值的，只需要修改下partition方法就可以了，本质上是一致的。
/// <summary>
/// 从大到小排序
/// </summary>
/// <param name="R"></param>
/// <param name="low"></param>
/// <param name="high"></param>
/// <returns></returns>
private static int Big_To_Small_Partition(int[] R, int low, int high)
{
int temp = R[high];
while (low < high)
{
while (low < high && temp <= R[low])
{
low++;
}
R[high] = R[low];
while (low < high && temp > R[high])
{
high--;
}
R[low] = R[high];
}
R[high] = temp;
return high;
}
