C++算法之在无序数组中选择第k小个数的实现方法分享

—-想了解C++算法之在无序数组中选择第k小个数的实现方法分享的全部内容且更多的C语言教程关注<计算机技术网(www.ctvol.com)!!>

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小个数的实现方法分享所述对大家C++程序设计有所帮助。