代码疑问
来源：3-9 归并排序和快速排序的衍生问题
weibo_瘦不下来的胖胖儿_0
2017-10-31
#include<iostream>
#include<algorithm>
#include<cassert>
using namespace std;
int arr[100];
int partition(int arr[],int l,int r)
{ if(l>=r)
return 0;
int v=arr[l];
int j=l,i=r;
while(j<i)
{
while(j<i&&arr[j]<v)
j++;
if(j<i)
{
arr[j]=arr[i];
i--;
}
while(j<i&&arr[i]>=v)
i--;
if(j<i)
{
arr[j]=arr[i];
j++;
}
}
return j;
}
int selection(int arr[],int l,int r,int k)
{
if(l==r)
return arr[l];
int p=partition(arr,l,r);
if(k==p)
return arr[p];
else if(k<p)
return selection(arr,l,p-1,k);
else
return selection(arr,p+1,r,k);
}
int main()
{
int n,i,k,c;
cin>>n;
int arr[n];
cin>>k;
for(i=0;i<n;i++)
cin>>arr[i];
c=selection(arr,0,n-1,k);
cout<<c<<endl;
return 0;
}
其他部分相同，只在main()函数部分有所改动，为什么不能得到正确的第n大的结果呢？
代码有疑问
1回答
-
liuyubobobo
2017-10-31
请确认算法代码是我的代码逻辑一致：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/Course%20Code%20(C%2B%2B)/Optional-05-Selection/main.cpp
注意，在这个代码中，k是从0开始计算的。也就是最小值k=0；第二小值k=1；...依次类推
如果确认了1，2点的话，具体是什么测试用例不能正确获得结果了呢？
042017-10-31
