查找第k个最小数-固定数组(c++版)

#include <iostream>
 
using namespace std;
  
int findK(int arrayNum[], int p, int r, int k) {
    /**
    *在数组arrayNum[p:r]中查找第k（k > 0)个元素（下标为p+k-1)
    * p <= r && 0 < k && k <= p - r +1 （合法输入说明）
    *渐进时间复杂度/平均时间复杂度 O(N)
    */
    int i = p, j = r, key = arrayNum[i];
    while (i < j) {
        while (i < j && arrayNum[j] >= key)
            --j;
        arrayNum[i] = arrayNum[j];
        while (i < j && arrayNum[i] <= key)
            ++i;
        arrayNum[j] = arrayNum[i];
    }//循环结束后 i = j,其实前面这些语句就是快排的一次划分
    arrayNum[i] = key;
    int lefts = i - p + 1;
    if (lefts == k) 
        return arrayNum[i];//找到中位数了
    if (lefts > k) //比关键字小的数的个数大于k，则中位数在左边
        return findK(arrayNum, p, i - 1, k);
    else
        return findK(arrayNum, i + 1, r, k - lefts);
}


int main()
{
    int tmp[10] = { 3, 4 , 5, 2, 4, 6,0, 8, 1,324 };
    cout<<"请输入要查找第几个最小数,数字要小于等于10"<<endl;
    int m=0;
    cin>>m;
    int result=0;
    result=findK(tmp,0,10,m);
    cout<<"结果为"<<result<<endl;
    
    return 0;
}

运行结果

请输入要查找第几个最小数,数字要小于等于10
7
结果为5