找出第k个最小的元素

电玩女神 2022-04-11 14:25 211阅读 0赞

/\*  
\*题目：编写程序，从数组x\[0...n-1\]中找出第k个最小的元素。算法可以对x中的元素进行排序  
\*/

\#include<stdio.h>  
\#include<time.h>  
\#include<stdlib.h>  
\#define LEN 10

typedef int dataType;

//初始化数组,数组元素为小于100的整数  
void intiArr(dataType A\[\], int len);  
//打印数组元素  
void print(dataType A\[\], int len);  
//找出第k小的数据并返回  
dataType findKMin(dataType A\[\],int len,int k);  
int main()  
\{  
int key;  
int k;  
dataType data\[LEN+1\];  
intiArr(data,LEN+1);  
data\[0\] = data\[1\];  
printf("数组元素：");  
print(data,LEN+1);  
printf("\\n输入k的值(比如，要查找第2小的数字，则输入2)，k值范围:1-%d\\nk=",LEN);  
scanf("%d",&k);  
if(k > LEN || k < 0)  
\{  
printf("输入k值错误，不在搜索范围内！\\n");  
return 0;  
\}  
key = findKMin(data,LEN,k);  
printf("\\n第%d小的元素是%d\\n",k,key);  
return 0;  
\}

//初始化数组,数组元素为小于100的整数  
void intiArr(dataType A\[\], int len)  
\{  
int i;  
srand((unsigned)time(NULL));  
for(i = 1; i < len; i++)  
\{  
A\[i\] = rand() % 100;  
\}  
\}

//打印数组元素  
void print(dataType A\[\], int len)  
\{  
int i;  
for(i = 1; i < len; i++)  
\{  
if((i-1) % 5 == 0)  
printf("\\n");  
printf("%d\\t",A\[i\]);  
\}  
\}

//找出第k小的数据并返回  
dataType findKMin(dataType A\[\],int len,int k)  
\{  
int start = 1;  
int end = len;  
int low;  
int high;  
do  
\{  
low = start;  
high = end;  
A\[0\] = A\[low\];  
//printf("A\[0\]=%d\\n",A\[0\]);  
while(low < high)  
\{  
while((low < high) && (A\[high\] >= A\[0\]))  
high--;  
A\[low\] = A\[high\];  
while((low < high) && A\[low\] <= A\[0\])  
low++;  
A\[high\] = A\[low\];  
\}  
A\[low\] = A\[0\];  
if(low == k)  
return A\[low\];  
else if(low < k)  
\{//第k小的元素在枢轴右边  
start = low + 1;  
end = len;  
\}  
else  
\{//第k小的元素在枢轴左边  
start = 1;  
end = low - 1;  
\}  
\}while(low != k);  
return 0;  
\}

![1357721590_1319.jpg][]

/\*博主寄语：如若发现错误，望指出，谢谢\*/

[1357721590_1319.jpg]: https://img-my.csdn.net/uploads/201301/09/1357721590_1319.jpg