N个元素数组中第K大元素

// K-key.cpp : 定义控制台应用程序的入口点。//

#include "stdafx.h"#include <time.h>#include <iostream>

using namespace std;

 

template <typename T>int pivotIndex(T arr[],int first,int last){   //随即产生一个pivotKey;   srand((unsigned)time(NULL));   int temp=rand()%(last-first+1)+first;

   //把arr[temp]与arr[first]交换   T pivotkey=arr[temp];   arr[temp]=arr[first];   arr[first]=pivotkey;

   while(first<last)   {     while((first<last) && (arr[last]>=pivotkey))      {      last--;     }     arr[first]=arr[last];

    while((first<last)&&(arr[first]<=pivotkey))     {      first++;     }      arr[last]=arr[first];      }//end while        arr[first]=pivotkey;    return first;}

template <typename T>T findK(T arr[], int first, int last, int K){ int index=pivotIndex<T>(arr,first,last);

 //计算arr[index]在数组中大小位置 int orderPosition=last-index+1;

 if(K==orderPosition)  //刚好找到 {  return arr[index]; } else if(orderPosition<K)//要找的元素在左边           {            return findK<T>(arr,first,index-1,K-orderPosition);           }          else  //要找的元素在右边    {            return findK<T>(arr,index+1,last,K);          }

}

int _tmain(int argc, _TCHAR* argv[]){ int arr[5]; int size=sizeof(arr)/sizeof(int); int K=2;    srand((unsigned)time(NULL)); for(int i=0;i<size;i++) {    arr[i]=rand()0;  }

 cout<<"The original arr"<<endl; for(int i=0;i<size;i++) {  cout<<arr[i]<<"/t";  }

 int MaxK=findK<int>(arr,0,size-1,K);

 cout<<"The "<<K <<"th"<<" Max is   "<<MaxK<<endl;

 return 0;}