Code666 (代码贴、代码片段)

[C++] 第K选择问题 →→→→→进入此内容的聊天室

来自 , 2021-03-07, 写在 C++, 查看 147 次.
URL http://www.code666.cn/view/d5c18698
  1. //第k选择问题  第k小问题
  2. #include<iostream>
  3. using namespace std;
  4. int partition(int r[],int first,int end)
  5. {
  6.         int i,j;
  7.         i=first;
  8.         j=end;
  9.         while(i<j)
  10.         {
  11.                 while(i<j&&r[i]<=r[j])
  12.                         j--;
  13.                 if(i<j)
  14.                 {
  15.                         swap(r[i],r[j]);
  16.                         i++;
  17.                 }
  18.                 while(i<j&&r[i]<=r[j])
  19.                         i++;
  20.                 if(i<j)
  21.                 {
  22.                         swap(r[j],r[i]);
  23.                         j--;
  24.                 }
  25.         }
  26.         return i;
  27. }
  28. int select(int a[],int m,int n,int r)
  29. {
  30.         int pos;
  31.         pos=partition(a,m,n);
  32.         if(pos==r) return r;
  33.         if(r<pos)
  34.                 return select(a,m,n-1,r);
  35.         else
  36.                 return select(a,m+1,n,r);
  37. }
  38. int main()
  39. {
  40.         int i,n,a[100],k;
  41.         cin>>n;
  42.         for(i=1;i<=n;i++)
  43.         {
  44.                 cin>>a[i];
  45.         }
  46.         cin>>k;
  47.         int pos;
  48.         pos=select(a,1,n,k);
  49. /*      cout<<zhouzhi(a,1,n)<<endl;//显示轴值位置
  50.         kuai(a,1,n);
  51.         for(i=1;i<=n;i++)
  52.         {
  53.                 cout<<a[i]<<" ";
  54.         }
  55.         cout<<endl;*/
  56.         cout<<a[pos]<<endl;
  57.         return 0;
  58. }

回复 "第K选择问题"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666