c读入n个不相同且不为0的数不用排序求出其中第r个大的数c读入n个不相同且不为0的数（1≤n≤100）不用排序求出其中第r个大的数（1≤r≤n）即有r-1个数比他大其余数比它小.

Question

c读入n个不相同且不为0的数 不用排序 求出其中第r个大的数
c读入n个不相同且不为0的数（1≤n≤100） 不用排序 求出其中第r个大的数（1≤r≤n） 即有r-1个数比他大 其余数比它小.

Answer 1

 求第K大的数,这是个很经典的题目,看到这个题目,很多人的第一反应就是：对这个
数组进行排序,然后直接去第k个数字就行了.的确,这是一个方法,不过是最笨的一个方
法,如果数据量很大的时候,光排序就占用了很多时间,而且楼主要求不能用排序,所以
得另辟蹊径! 
  对一组数据进行排序,最快的要数快排序了,其中快排序中最核心的partion函数就是确
定一个数的最终位置,这个位置前面部分的数要比这个数小,这个位置后面部分的数都比
这个数大,然后再对前后两个部分进行递归运算,最后就得出一个有序的数组.
  在这里,我们就可以运用快排序的思想,直接求出第k个位置上的数
  比如说,我们第一次调用partion函数,它返回一个索引index,如果index比k大,说明
应该在index的前面部分循环调用partion,如果比较小就在后面部分调用partion,知道最
后index正好等于k,这个k就是排序后的有序数组中的k,也就是第k大了,空口无凭,上代
码,并附有我运行调试的结果.
int  partion(int a[],int left,int right)//此函数,是寻找一个数组元素在排序后的
最终位置
{
 
 int temp=a[left];
 while(left {
  while(temp<=a[right]&&left   --right;
  a[left]=a[right];
  while(temp>=a[left]&&left   ++left;
  a[right]=a[left];
 }
 a[left]=temp;
 return left;
}
int  FindKth(int a[],int n,int k)//寻找第k大,返回值就是需要找的k
 {
  int index;
  index=partion(a,0,n-1);
  while(index!=k)
  {
   if(index    index=partion(a,index+1,n-1);
   else
    index=partion(a,0,index-1);
  }
  return index;
 }
为了让楼主看的更明白,我把原始数据用快速排序法,排序后显示,此题可以不用.下面
是快速排序法：
void quicksort(int a[],int left ,int right)//快速排序
{
  int index;
  if(left  {
 
   index=partion(a,left,right);
   quicksort(a,left,index-1);
   quicksort(a,index+1,right);
  }
}
void Quick_sort(int a[],int left,int right)//显示快速排序后的数组元素
{
 quicksort(a,left,right);
 cout< for(int i=0;i<=right;i++)
  cout<}