线性时间选择.txt

这是另外一个线性时间选择的代码。大家看看吧

import java.util.Date;
import java.util.Random;

public class Select {
 
 private static int randomPartition(int[] data, int start, int end) {
  Random rand = new Random(new Date().getTime());
  int index = rand.nextInt(data.length);
  swap(data, 0, index);
  return partition(data, start, end);
 }
 private static int partition(int[] data, int start, int end) {
  int var = data[start];
  int i = start + 1;
  int j = end;
  for (;;) {
   while (data[i] < var)
    i++;
   while (data[j] > var)
    j--;
   if (i >= j)
    break;
   else
    swap(data, i, j);

  }
  data[start] = data[j];
  data[j] = var;
  return j;
 }

 private static void swap(int[] data, int i, int j) {
  int temp = data[i];
  data[i] = data[j];
  data[j] = temp;
 }

 public static int select(int[] data, int start, int end, int k) {
  if (start == end)
   return data[start];

  int mid = randomPartition(data, start, end);
  int size = mid - start + 1;
  if (k <= size)
   return select(data, start, mid, k);
  else
   return select(data, mid + 1, end, k - size);

 }
 
 public static void main(String[] args) {
  int[] data = {2, 1, 4, 5, 3,};
  System.out.println(select(data, 0, data.length - 1, 5));
 }
}

2
#include<iostream.h>

#include<stdlib.h>

#include<time.h>

#define MAX_VALUE 10000

#define random() rand()%MAX_VALUE

#define N 10000

int a[N];

class Find

{

public:

       void bubble(int first,int end) //冒泡排序

       {     

for(int flag=first;flag<end;flag++)

                     for(int i=end;i>flag;i--)

                            if(a[i]<a[i-1])

                            {     int t=a[i];

                                   a[i]=a[i-1];

                                   a[i-1]=t;

                            }

       }

       int partition(int p,int r,int x) //数组a中从a[p]到a[r]的元素按照x划分,大于x的在左边,小于x的在右边

       {  

 int i,j;

              for(i=p,j=r;i<j;i++)

              {     

if(a[i]>x)

                     {     

while(i<j&&a[j]>x)

                                   j--;

                            if(i!=j){

                                   int t=a[i];

                                   a[i]=a[j];

                                   a[j]=t;

                                   j--;

                            }

                     }

              }

              return i-1;

       }

       int select(int p,int r,int k)   //寻找中位数

       {

              if(r-p<5){

                     bubble(p,r);

                     return a[p+k-1];

              }

              for(int i=0;i<(r-p-4)/5;i++)

              {

                     int s=p+5*i,t=s+4;

                     bubble(s,t);

                     int temp=a[p+i];

                     a[p+i]=a[s+2];

                     a[s+2]=temp;

              }

              int x=select(p,p+(r-p-4)/5,(r-p+6)/10);

              i=partition(p,r,x);

              int j=i-p+1;

              if(k<=j)

                     return select(p,i,k);

              else

                     return select(i+1,r,k-j);

       }

};

void main()

{

       clock_t   start,end;   

       double   elapsed;

       srand((int)time(NULL));

       for(int k=0;k<N;k++)

       {

              a[k]=random();

              cout<<a[k]<<"\t";

       }

       cout<<endl;

       start=clock();

       Find f;     

       int n=5000;

       cout<<"The No."<<n<<" is :"<<f.select(0,N-1,n)<<endl;

       end=clock();

       elapsed=((double)(end-start));///CLOCKS_PER_SEC; 

       cout<<"Time: "<<elapsed<<endl;

}