C语言 对于给定的N各元素的数组[0;N-1],要求从中找出第K小的元素

C语言 对于给定的N各元素的数组[0;N-1],要求从中找出第K小的元素

有两种方法可以实现：
1 对数组进行从小到大排序，排序方法任意。
在排序后，数组的第K个元素即为第K小的元素。

2 对于N值较大，K值较小的情况，1中的时间开销偏大。
这时可以用额外的空间开销，来换取更高的效率。
方法为：
a) 开辟一个K个元素的临时空间M；
b) 取数组中的第一个元素，置于M中；
c) 取第二个元素，插入到M中，保证M中是从小到大排序的；
d)对于后续N中的每个元素，均自后向前遍历M，并插入到M对应位置中，保证M有序；
e)如果M中已经有K个元素，那么在插入时，新元素如果比结尾元素更大，则不插入，否则插入到对应位置，原本最后一个元素抛弃；
f)当对N的遍历结束后，存储于M中的，就是K个N中的最小元素的有序序列。此时第K个元素，就是要求的的结果。

C语言趣味程序百例精解 百度一下前面的内容，是PDF的自己看看吧，超有用的。我只能说，原作者很好很强大！

这是根据你的程序，对程序进行了些修改，基本能够跑通。
希望能够帮到你
void swap(int*x,int*y);
int select(int a[],int left,int right, int k)
{
int i,j,pivot;
if(left>=right)
return a[left];
pivot=a[left];
i=left;
j=right+1;
while(1)
{
do{
}
while(a[++i] do{
}
while(a[--j]>pivot&&j>=left);//多加了个判断条件
if(i>=j)break;
swap(&a[i],&a[j]);
}
if(j-left+1==k) return pivot;
//边界情况判断
if (j==right&&i==right+1) {
return select(a,left+1,right,k);
}
if (j==left&&i==left+1) {
return select(a,left+1,right,k-1);
}
if(j-left+1 return select(a,j+1,right,k-j-1+left);
}

else{
a[left]=a[j];
a[j]=pivot;
return select(a,left,j-1,k);
}
}
void swap(int *x,int *y)
{
int t;
t=*x;
*x=*y;
*y=t;
}
void main(){
int array[20]={1,2,3,4,5,6,7,8,9,10,11,31,12,15,18,20};

printf("%d \n;",select(array,0,9,5));
}

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息