自己寫的尋找數(shù)組中第k大元素的函數(shù)，采用二分查找法，平均時(shí)間復(fù)雜度O(logN)，有更好的方法歡迎指正
感謝 同學(xué)指正，我重新思考了一下次算法的時(shí)間復(fù)雜度
理想情況下如果每次都正好分到中間的話，每次比較的次數(shù)就是公比為0.5的等比數(shù)列，也就得到
T(N)=a1(1-q^n)/(1-q) =N(1-0.5^(logN))/0.5=2N-0,5^(logN-1)
當(dāng)N→∞時(shí)，得平均時(shí)間復(fù)雜度為O(N)
但是本算法的最壞情況確實(shí)O(N^2)
/**//************************************************************************/
/**//* find the k bigger number in the array, using Bisection method
/* Contact:lyi.tech@gmail.com
/* 2011-3-10
/************************************************************************/
int findKBiggest(int *array,int begin,int end,int k);
int nonrecursive_FindKBiggest(int *array,int length,int k);
void switch2(int *a,int *b);
//************************************
// Method: findKBiggest
// FullName: findKBiggest
// Access: public
// Returns: int
// Qualifier:
// Parameter: int * array
// Parameter: int length
// Parameter: int k
// Parameter: int * k_value
// the K biggest number,the biggest number is labeled by 1
//************************************
int findKBiggest(int *array,int length,int k,int *k_value)
{
if (k>length||k<1||length<1)
return -1;
else
{
//*k_value=findKBiggest(array,0,length-1,k);
*k_value=nonrecursive_FindKBiggest(array,length,k);
return 0;
}
}
//************************************
// Method: recursive method
// FullName: findKBiggest
// Access: public
// Returns: the K biggest number,the biggest number is labeled by 1
// Qualifier:
// Parameter: int * array
// Parameter: int begin
// Parameter: int end
// Parameter: int k base on 1
//************************************
int findKBiggest(int *array,int begin,int end,int k)
{
int tmpbegin=begin;
int tmpend=end;
int *tmp=array+begin++;
int length=end-begin+1;
while (1)
{
while ((*(array+begin) >= *tmp)&&(begin<tmpend))
begin++;
while ((*(array+end) < *tmp)&&(end>tmpbegin))
end--;
if (begin<end)
{
switch2(array+begin,array+end);
}
else
{
switch2(tmp,array+end);
break;
}
}
if (end+1==k)
return *tmp;
else if(end+1<k)
return findKBiggest(array,end+1,tmpend,k);
else
return findKBiggest(array,tmpbegin,end-1,k);
}
void switch2(int *a,int *b)
{
if (a!=b)
{
*a=*a+*b;
*b=*a-*b;
*a=*a-*b;
}
}
//************************************
// Method: nonrecursive method
// FullName: nonrecursive_FindKBiggest
// Access: public
// Returns: the K biggest number,the biggest number is labeled by 1
// Qualifier:
// Parameter: int * array
// Parameter: int length
// Parameter: int k
//************************************
int nonrecursive_FindKBiggest(int *array,int length,int k)
{
int begin=0,end=length-1;
int tmpbegin,tmpend;
int posnow=0;
while (1)
{
tmpbegin=begin+1;
tmpend=end;
while (1)
{
while (*(array+tmpbegin) >= *(array+begin) && tmpbegin<end)
tmpbegin++;
while (*(array+tmpend) < *(array+begin) && begin < tmpend)
tmpend--;
if (tmpbegin<tmpend)
{
switch2(array+tmpbegin,array+tmpend);
}
else
{
switch2(array+begin,array+tmpend);
break;
}
}
if (k==tmpend+1)
break;
else if(k>tmpend+1)
begin=tmpend+1;
else
end=tmpend-1;
}
return *(array+tmpend);
}