Problem Solving using C++

Algorithm Study using C++

选择算法--Random Select

从一个乱序数组A[1....n]中选择排第i的数,就是经典的选择select问题
最Naive的办法就是先对整个数组进行排序(可以使用quicksort/merge sort/heap sort)但是其算法复杂度为O(nlogn),如果使用quicksort的partition的变种的话,其最差复杂度为O(n^2),但是平均复杂度为O(n).其核心算法如下:
int randselect(int p,int r,int i)
{
    if(p==r)
          return arr[p];
   int q = partition(p,r);//调用quicksort里面的partition
   int k = q-p+1;
   if(i==k)
           return arr[q];
   if(i<k)
           return randselect(p,q-1,i);
   if(i>k)
           return randselect(q+1,r,i-k);
}

代码如下:

#include <iostream>
#include 
<iterator>
#include 
<algorithm>
#include 
<cstdlib>

using namespace std;

#define MAXSIZE    
100
int arr[MAXSIZE];

void fillarray()
{
    
for(int i=0;i<MAXSIZE;i++)
    {
        arr[i]
=rand()%MAXSIZE;
    }
}

void print(bool flag=true)
{
    
if(flag)
    {
        copy(arr,arr
+MAXSIZE,ostream_iterator<int>(cout," "));
        cout
<<endl;
    }
}

int partition(int p,int r)
{
    
int pivot = arr[r];
   
    
int i=p-1;
    
for(int j=p;j<r;j++)
    {
        
if(arr[j]<pivot)
        {
            i
++;
           
            
int temp = arr[j];
            arr[j]
=arr[i];
            arr[i]
=temp;
        }
    }
   
    arr[r]
=arr[i+1];
    arr[i
+1]=pivot;
   
    
return i+1;
}

void quicksort(int p,int r)
{
    
if(p<r)
    {
        
int q=partition(p,r);
        quicksort(p,q
-1);
        quicksort(q
+1,r);
    }
}

int randselect(int p,int r,int i)
{
    
if(p==r)
        
return arr[p];
       
    
int q = partition(p,r);
    
int k = q-p+1;
    
if(i==k)
        
return arr[q];
    
if(i<k)
        
return randselect(p,q-1,i);
    
if(i>k)
        
return randselect(q+1,r,i-k);
}

int main(int argc,char* argv[])
{
    fillarray();
    print();
   
    
//quicksort(0,MAXSIZE-1);
    
//print();
    for(int i=0;i<MAXSIZE;i++)
        cout
<<randselect(0,MAXSIZE-1,i+1)<<" ";
   
    cout
<<endl;
   
    system(
"pause");
    
return 0;
}

posted on 2007-08-23 10:35 Kingoal Lee's Alogrithm Study using cplusplus 阅读(627) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


My Links

Blog Stats

常用链接

留言簿(1)

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜