快速选择算法(时间复杂度o(n)

选择问题是求一个n个数列表的第k个最小元素的问题。
中位数：百度百科定义如下：
      对于有限的数集，可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个，通常取最中间的两个数值的作为中位数。
中轴p(列表中的第一个元素) Lomuto划分
      考虑一个数组，或者更一般的一个字数组A[l...r](0≤l≤r≤n-1),该数组由连续的3段组成。这3段按顺序排在中轴p的后面：一段为已知小于p的元素，一段为已知大于或等于p的元素，还有一段未同p比较过的元素。这些段可以为空，在算法开始时，前两段通常是空的。
在i= l+1开始，算法从左到右扫面字数组A[l...r],并保持这个结构直到划分完成。在每一次迭代中，它把未知段中的第一个元素与中轴p进行对比。如果A[i] >= p,则只要i+1就扩大了大于等于p元素的段，而同时缩小了未处理的段。  数组中第k小元素的快速选择算法的c代码如下： 

#include<stdio.h>
#include<stdlib.h>
#define swap(t,x,y) (t = (x),x = (y),y = (t))
int lomutoPartition(int *a,int lo,int hi)
{
    int s = lo;
    int i = lo+1;
    int p =a[lo];
    int temp = 0;
    for (i = lo+1;i < hi;i++)
    {
        if (a[i] < p)
        {
            s = s+1;
            swap(temp,a[i],a[s]);
        }
    }
    swap(temp,a[lo],a[s]);
    return s;
}
int quickselect(int *a,int lo,int hi,int k)
{

        int s = lomutoPartition(a,lo,hi);
        if (lo+k-1 == k) return a[s];
        else if (lo+k-1 < s) quickselect(a,lo,s-1,k);
        else quickselect(a,s+1,hi,lo+k-s-1);//这里lo别忘记写

}
int main()
{
    int a[4] = {1,2,3,4};
    int result = quickselect(a,0,3,2);
    printf("%d\n",result);
    return 0;
}

具体见下一篇文章