线性时间求中位数 选择任意大or小的数

   今天看一个找工作经验,上面提到线性时间求中位数.想想难道用桶排序？？？再次见证自己的孤陋寡闻。没有好好看书,算法导论中位数那一章明明就有以期望线性时间做选择。大概思路就是用到了快排的思路,不过分成左右后不是再两边都快排,而是只快排一边的了。

    我举个例子好了

    1   6   9   8   2   3  5   4

    假设你现在以4快排

    1   2   3   4   6   9  5   8

    这个时候你是求第3小的数,Ok那你就只用对

    1 2 3 快排了.. 6  9    5  8就不用了,而快排就还需要

 

   好了看程序吧,我程序里面也用到了快排,方便看看第k小的数是不是对的以及给大家看看这两种的处理方式具体是在哪里不一样

    

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 20

void init_a(int A[])
{
  int i = 0;
  for(;i<N;i++)
   A[i] = rand()%100;
 }
 
void print_array(int A[])
{
   int i = 0;
   for(;i<N;i++)
    {
     if(i==9)
      printf("%d\n",A[i]);
     else
      printf("%d\t",A[i]);
    }
 }

void swap(int* a, int* b)
{
   int tmp = *a;
   *a = *b;
   *b = tmp;
 }
 
int rand_partition(int A[], int start, int end)
{
   int i = start-1;
   int j = start;
   int num = rand()%(end-start+1)+start;
   swap(A+num,A+end);
   int x = A[end];
   
   for(;j<end;j++)
    {
      if(A[j]<=x)
       {
         i++;
         swap(A+i,A+j);
        }
     }
   swap(A+i+1,A+end);
 
   return i+1;
}


int random_select(int A[], int start, int end, int k)
{
  int i = 0;
  if(start == end)
    return A[start];
    
  int q = rand_partition(A, start, end);
  i = q-start+1;
  
  if(i == k)
    return A[q];
  else if(i<k)
    return random_select( A, q+1, end, k-i);
  else
    return random_select( A, start, q-1, k);
}

void quick_sort(int A[], int start, int end)
{
  if(start<end)
   {
     int q = rand_partition(A, start, end);
  
     quick_sort( A, q+1, end);
     quick_sort( A, start, q-1);
  }
}
   
int main(int argc, char *argv[])
{
  int A[N];
  int num = 0;
  int res = 0;
  srand((unsigned)time(NULL));
  init_a(A);
  print_array(A);
  
  num = rand()%(N-10)+5;
  printf("we begin select %d minimun number\n",num);
  res = random_select( A, 0 , N-1, num);
  printf("and num is %d\n",res);
  
  quick_sort( A, 0 , N-1);
  printf("after quick sort the array is:\n");
  print_array(A);
  system("PAUSE");    
  return 0;
}