3.txt

求第K个最小值 比2分法还快的算法 只要比N-1次就行

#include<stdio.h>

#define MAXSIZE 100
typedef int datatype;
typedef struct
{datatype data[MAXSIZE];
  int last; 
 }SeqList;

int n,i;
SeqList *CreatSeqList()          /*输入数建立链表*/
{SeqList *q;
 int x2;
q=(SeqList *)malloc(sizeof(SeqList));
printf("输入%d个数:\n",n);
while(i<n)
  {scanf("%d",&x2);
    q->data[i]=x2;
  i++;
}
q->last=n-1;
return q;

}

datatype part(SeqList *q,int a,int b,int k)
{ 
    int i,j; 
    datatype m,t;

    m=q->data[a+k-1], q->data[a+k-1] = q->data[b],q->data[b] = m;
    for (i=a-1, j = a; j != b; ++j)
        if (q->data[j] < m)
            t=q->data[++i], q->data[i]=q->data[j], q->data[j]=t;
    t=q->data[++i], q->data[i]=q->data[j], q->data[j]=t;

    if (k==i-a+1) return m;
    if (k>i-a+1) return part(q, i+1, b, k-i+a-1);
    else        return part(q, a, i-1, k);
} 


main()
{SeqList *q;
datatype A;
  int k;
 printf("输入个数:\n");
 scanf("%d",&n);

q=CreatSeqList();

printf("输入K值:\n");
scanf("%d",&k);
A=part(q,0,q->last,k);
 printf("第%d个最小值为: %d\n",k,A);
getch();
return 0;
 }