求第K大的数以及其位置

   写一段程序，找出数组中第k大的数，输出数所在的位置。例如{2，4，3，4，7}中，第一大的数是7，位置在4。第二大、第三大的数都是4，位置在1、3随便输出哪一个均可。
函数接口为：int find_orderk(const int* narry,const int n,const int k)

 

   求第k大的数其实大家首先想到的肯定是heap排序,就是先对k个大树排序,然后在遍历原数组...但是这样位置就不好处理,我这里想的是快速排序,这样第一次排好序后,就可以求出任意大的数以及其原来的位置了.一家之言.不求大同...

      主要就是附加了一个SEQ数组来表示位置,我先还想到把原来的位置和值弄成一个struct....

其实觉得BT点的就是在数不太大的情况下把高几位用于记录原先的位置,快排比较的时候取余就可以了.好了,不废话了

 

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

#define MAX_NUMS 20
#define MAX_VAL 100

int SEQ[MAX_NUMS];

void init_seq()
{
    int i = 0;
    for(;i<MAX_NUMS;i++)
     {
       SEQ[i] = i+1;
      }
 }
 
int getrandval()
{
   return rand()%MAX_VAL+1;
 }

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

int quicksort(int A[], int start, int end)
{
  int q = 0;
  if(start<end)
   {
     q = quickpartition( A, start, end);
     quicksort( A, start, q-1);
     quicksort( A, q+1, end);
    }
}

int printf_arrray(int A[])
{
  int i = 0;
  for(;i<MAX_NUMS;i++)
   {
     if((i+1)%10==0)
      printf("%d\n",A[i]);
     else
      printf("%d\t",A[i]);
    }
}
   
int main(int argc, char *argv[])
{
  int i = 0;
  int A[MAX_NUMS];
  int k = 0;
  srand((unsigned)time(NULL));
  init_seq();
  
  for(;i<MAX_NUMS;i++)
   {
     A[i] = getrandval();
    }
  printf("before quick sort:\n");
  printf_arrray(A);
  quicksort(A, 0, MAX_NUMS-1);
  printf("after quick sort:\n");
  printf_arrray(A);
  
  k = rand()%MAX_NUMS;
  printf("the %d larger num is %d and the seq is %d\n", k+1, A[k], SEQ[k]);
  system("PAUSE");    
  return 0;
}