线性时间选择1

#include "stdio.h"

int partion(int a[], int left, int right)
{    //将小于数组a[]第一个元素的元素移到左区间，将大于a[0]的元素移到右区间
int i = left;
int j = right;
int temp = a[left];
while(i<j)  
    {
while(i<j && a[j]>temp)  //如果右边元素大于参照元素
            j--;    //右面区间下标左移
        a[i] = a[j];    //将右边小于参照元素的元素移到左区间
while(i<j && a[i]<temp)   //如果左边元素小于参照元素
            i++;   //左面下标右移
        a[j] = a[i];    //将左边大于参照元素的元素移到右区间
    }
    a[i] = temp;    //将参照元素放置到合适的位置
return i;    //返回参照元素下标
}

int select(int a[], int left, int right, int k) //在a[left:right]中选择第k小的元素并返回
{
if(left == right)
return a[left];
int mid = partion(a, left, right);  //a[left:mid]中每个元素都不大于a[mid+1:right]中的元素
int j = mid - left + 1;   //左半区间长度
if(k<=j)    //如果第k小元素落在字数在a[left:mid]中
return select(a, left, mid, k);   //在a[left:mid]中寻找第k小元素
else
return select(a, mid+1, right, k-j);   //在a[mid+1:right]中寻找第k-j元素
}

int main()
{
int a[100];
int len;
int i, k;
printf("输入元素个数：");
scanf("%d", &len);
printf("输入元素：");
for(i=0; i<len; i++)
scanf("%d", &a[i]);
printf("想要查找第k小元素：k=");
scanf("%d", &k);
int f = select(a, 0, len-1, k);
printf("%d\n", f);
return 0;
}