找无序数组中第k小的数

问题遇到的现象和发生背景

想设计一个平均时间为O(n)的算法，在n(1<=n<=1000)个无序的整数中找出第k小的数。

用代码块功能插入代码，请勿粘贴截图

#include
using namespace std;
int partition(int a[],int p,int r)
{
    int i,j,t;
    i=-1,j=0;
    while(jif(a[j]<=a[r])   //need"=" 
        {
            t=a[i+1],a[i+1]=a[j],a[j]=t;
            i++,j++;
        //    cout<<"xxx" <else
        {
            j++;
        //        cout<<"ooo" <1],a[i+1]=t;
    //cout<1];
    return i+1;
}


int find(int a[],int p,int r,int k)
{   if(pint q=partition(a,p,r);
    if(q==k-1) {
    return a[q];}
    else if (q-1)  find(a,q+1,r,k);
    else if (q>k-1)  find(a,p,q-1,k);
}

}

int main()
{
    int a[2000];
    int n,k;
    cin>>n>>k;
    for(int i=0;i>a[i];
    
         cout<0,n-1,k); //绛旀
         cout<<"   test point: "; 
        for(int i=0;i

运行结果及报错内容

这个3到底是哪里来的啊？
我数组里都没有3

我的解答思路和尝试过的方法

就是一边划分一边比较其中心点地址与k来判断是否符合要求

我想要达到的结果

输入：6 4
1 1 4 5 1 4

输出：4

示例中的3到底是怎么出来的求解答

完全没看出来这个算法怎么能是O(n)的时间复杂度。用了类似二分的递归，怎么也不会是O(n)啊
而且逻辑也没看明白。
假设是 5 6 4 3 2 1 你这处理顺序是什麽呢？和最右边的值比较，为什麽呢？
find函数有两个漏洞，一是只考虑p<r，当p>=r时，没有返回值，导致函数没有返回值；二是递归函数应该为 return find(a,q+1,r,k);这样子，否则也是没有返回值。由于没有正确返回值，所以main你cout出来的3是个垃圾值而已。实际你的代码找不到第4小的数

你不是有cout输出吗
cout<<find(a,0,n-1,k);
这里返回的结果值。

#include<iostream>
using namespace std;

int partition(int a[],int left,int right){
int i = left+1,j = right;
int x = a[left];
while(i<=j){
while(a[i] <= x && i < right) i++;
while(a[j] > x) j--;
if(i >= j) break;
int m;
m = a[j];
a[j] = a[i];
a[i] = m;
}
a[left] = a[j];
a[j] = x;
return j;
}

int find(int a[], int left, int right, int k)
{
if (left == right)
return a[left];
int i = partition(a, left, right);
int j = i - left + 1;
if (k <= j)
return find(a, left, i-1, k);
else
return find(a, i + 1, right, k - j);

}

int main(){
int n,k;
cin>>n>>k;
int arr[10000];
for(int i=0;i<n;i++){
cin>>arr[i];
}
int q = find(arr,0,n,k);
cout<<q<<endl;
return 0;
}

您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632