怎么使用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小个数”这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注亿速云行业资讯频道。