随机算法.cpp

用分治法实现找K小元素

//随机算法，基于快速排序的思想，是O（N）的算法

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define LEN 1024 

int RANDOM(int p,int r)
{
    return rand()*(r-p)/32767+p;    
}
int PARTITION(int arr[LEN],int p,int r)
{
     int x = arr[r];
     int i = p-1;
     for(int j = p;j<r;j++)
     {
         if(arr[j]<=x) 
         {
            ++i;
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;   
         }
     }
     int t = arr[i+1];
     arr[i+1] = arr[r];
     arr[r] = t;
     return i+1;     
}
int RANDOMIZED_PARTITION(int arr[LEN],int p,int r)
{
     int i = RANDOM(p,r);
     int t = arr[i];
     arr[i] = arr[r];
     arr[r] = t;
     return PARTITION(arr,p,r);
}
int RANDOMIZED_SELECT(int arr[LEN],int p,int r,int i)  //找到arr中第i小的数，数组下标从1开始 
{
     if(p==r) return arr[p];
     int q = RANDOMIZED_PARTITION(arr,p,r);
     int k = q-p+1;
     if(i==k) return arr[q];
     else if(i<k)
     return RANDOMIZED_SELECT(arr,p,q-1,i);
     else return RANDOMIZED_SELECT(arr,q+1,r,i-k);      
}
int main()
{
    int n,arr[]={45,67,32,78,4,23,567,78,34,0,78};
    while(scanf("%d",&n)==1)
    {
         printf("%d\n",RANDOMIZED_SELECT(arr,0,10,n));                   
    }
    return 0;
}