最直观的解法，排序之后取下标为k的值即可。
但是此处采取的方法为类似快速排序分块的方法，利用一个支点将序列分为两个子序列（支点左边的值小于支点的值，支点右边大于等于支点的值）。
如果支点下标等于k，则支点就是查找的值，如果支点的下标大于k，则在左子序列里继续寻找，如果支点下标小于k，则继续在支点右子序列里面继续寻找第（k-支点下标）小的值。
c#实现算法如下：
public class FindSpecialOrderElement<T> where T : IComparable<T>
{
public T FindElementWithOrder(T[] array, int startIndex, int endIndex, int order)
{
int pivot = Partition(array, startIndex, endIndex);
//pivot支点为第（pivot-startIndex+1）小的值
int pivotOrder = pivot - startIndex + ;
if (pivotOrder == order)
{ return array[pivot]; }
else if (pivotOrder > order)
{
return FindElementWithOrder(array, startIndex, pivot - , order);
}
else//pivotOrder < order
{
return FindElementWithOrder(array, pivot + , endIndex, order - pivotOrder);
}
}
public static int Partition(T[] array, int leftIndex, int rightIndex)
{
//leftIndex的位置空出来了
T pivotValue = array[leftIndex];
//将所有<pivotValue的值移动到pivotValue的左边（不稳定排序，因为相等值得相对位置可能被此步骤改变）
//将所有>=pivotValue的值移到右边
//移动的结果就是所有<pivotValue的值都在pivotValue的左边，>=它的都在右边
//记录之后pivotValue所在位置，返回该位置，完成一次分区划分。
while (leftIndex < rightIndex)
{
//因为是leftIndex先空出来位置，所以第一步要从右侧rightIndex向左寻找小于pivotValue的数值位置
while (leftIndex < rightIndex && array[rightIndex].CompareTo(pivotValue) >= ) rightIndex--;
//将找到的小于pivotValue的位置的元素放到空出的leftIndex位置，leftIndex++
if (leftIndex < rightIndex) array[leftIndex++] = array[rightIndex];
//leftIndex向右寻找>=pivotValue的值的位置
while (leftIndex < rightIndex && array[leftIndex].CompareTo(pivotValue) < ) leftIndex++;
//将找到的>=pivotValue的位置的leftIndex元素放到上一步空出的rightIndex位置
//此时leftIndex所在位置变成待插入位置，重新回到外圈循坏的初始状态
if (leftIndex < rightIndex) array[rightIndex--] = array[leftIndex];
}
//最后while循环结束的位置就是leftIndex==rightIndex，并且这个位置是空出来的，正好把pivotValue放到这个位置
//这就是轴的概念，轴两边的值时由轴正好分开的，一边小于轴，一边大于等于轴
array[leftIndex] = pivotValue;
return leftIndex;
} }
方法调用方法：
static void Main(string[] args)
{
FindSpecialOrderElement<int> ESOE = new FindSpecialOrderElement<int>();
int[] data1 = new int[] { , , , , , , , , , };
Console.WriteLine();
data1.ToList<int>().ForEach(i => Console.Write("{0},", i));
int e = ESOE.FindElementWithOrder(data1, , data1.Length - , );
Console.WriteLine("Find the 4th small element:{0}", e); int[] data2 = new int[] { , , , , , , , , , };
Console.WriteLine();
data2.ToList<int>().ForEach(i => Console.Write("{0},", i));
int f = ESOE.FindElementWithOrder(data2, , data1.Length - , );
Console.WriteLine("Find the 7th small element:{0}", f);
Console.ReadKey();
}
作者：Andy Zeng
欢迎任何形式的转载，但请务必注明出处。
http://www.cnblogs.com/andyzeng/p/3695478.html