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

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

创新互联建站是网站建设专家,致力于互联网品牌建设与网络营销，专业领域包括成都网站建设、做网站、电商网站制作开发、重庆小程序开发公司、微信营销、系统平台开发，与其他网站设计及系统开发公司不同，我们的整合解决方案结合了恒基网络品牌建设经验和互联网整合营销的理念，并将策略和执行紧密结合，且不断评估并优化我们的方案，为客户提供全方位的互联网品牌整合方案！

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

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

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

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

            文章转载：http://cxhlcq.com/article/iejecc.html