怎么使用C++在无序数组中实现选择第k小个数

今天小编给大家分享一下怎么使用C++在无序数组中实现选择第k小个数的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。

从一个无序的整型数组中选出第k小的数，如k=1为最小数，k=n为最大数。这里数组可以是有重复的值！

下面是自己写的一个函数，记在此处来记忆我留下的痕迹！

//选择无序数组中第k小的数 #include <iostream> using namespace std ; bool failed = false ; //这里只考虑数组是int型的 int findnumber(int *array,int start , int end, int k) {   if(array == NULL || start > end || k < start || k > end+1 || k <= 0 )   {     failed = true ;     return 0;   }   if(start == end)   {     return array[start] ;   }   int len = end - start + 1 ;   int tmp = 0 ;   int ps = rand()%len +start ;   int tk = k ;   while(true)   {    //分割两数组    int f = start ;    int t = array[ps] ;    int equalnum = 0 ;    for(int i = start ; i <= end ; i ++ )    {         if(array[i]< t )         {           tmp = array[f];           array[f] = array[i];           array[i] = tmp ;           f ++ ;         }else if(array[i] == t)         {           tmp = array[f];           array[f] = array[i];           array[i] = tmp ;           f ++ ;           equalnum ++ ;         }     } //end     f--;     if(equalnum > tk && (f - start + 1) == equalnum)     {       return t ;//这里是记录数据相等的数目，当我们从开始start处到最后处end都被这个值给充斥了，那么肯定是这里面的值了，再进行下去就会陷入死循环了。     }     if(tk == (f - start + 1) )     {       return t ;     }     if((f - start + 1 ) > tk )     {       end = f ;     }else     {        start = f + 1  ;        tk = k - start  ; //这个地方犯过错误，就是写成了k=k-start，在调试的时候老发现无限的循环。后来打印k的值的时候发现k的值都***为负了。这个bug，这个过错使得在一次运行可能会得到正确的数据，但是多次运行后程序就崩溃。      }      len = end - start + 1 ;      ps = rand()%len +start ;   } } int main() {   int array[10] = {1,1,1,2,2,1,4,1,1,1};   for(int i = 0 ; i < 10 ; i ++ )   {     cout<<findnumber(array,0,9,i+1)<<endl;   }   system("pause");   return 0 ; }

以上就是“怎么使用C++在无序数组中实现选择第k小个数”这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注亿速云行业资讯频道。