//選擇無(wú)序數(shù)組中第k小的數(shù)
#include <iostream>
using namespace std ;
bool failed = false ;
//這里只考慮數(shù)組是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)
  {
   //分割兩數(shù)組
   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 ;//這里是記錄數(shù)據(jù)相等的數(shù)目，當(dāng)我們從開始start處到最后處end都被這個(gè)值給充斥了，那么肯定是這里面的值了，再進(jìn)行下去就會(huì)陷入死循環(huán)了。
    }
    if(tk == (f - start + 1) )
    {
      return t ;
    }
    if((f - start + 1 ) > tk )
    {
      end = f ;
    }else
    {
       start = f + 1  ;
       tk = k - start  ; //這個(gè)地方犯過(guò)錯(cuò)誤，就是寫成了k=k-start，在調(diào)試的時(shí)候老發(fā)現(xiàn)無(wú)限的循環(huán)。后來(lái)打印k的值的時(shí)候發(fā)現(xiàn)k的值都***為負(fù)了。這個(gè)bug，這個(gè)過(guò)錯(cuò)使得在一次運(yùn)行可能會(huì)得到正確的數(shù)據(jù)，但是多次運(yùn)行后程序就崩潰。
     }
     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 ;
}