爱魔域

[Quote=引用 2 楼 ohmygirl 的回复:]
else if(k<j){
vector<int> A1 ;
for(int i=0;i!=j-1;i++)
(A1).push_back(A[i]);
return Select2(A1,k);// K比J小在A[0]-A[j-2]中求第K小元素
}

应该是， K比J小在A[0]-A[j-1]中求第K小元素

C/C++ code


e……
[/Quote]


#include <iostream>
#include <vector>
using namespace std;
const int r = 5;
void insertsort(vector<int> &vint,int begin,int end)//快速插入排序
{
int j=0;
int temp;
for(int i=begin;i!=end;i++)
{
//a[0]=a[i];
temp=(vint)[i];
j=i- 1;
while(j>=begin && temp<(vint)[j])
{
(vint)[j+1]=(vint)[j];
j--;
}
(vint)[j+1]=temp;
}
}
//快速排序分类，俺temp的值将A中的值分为两部分，第一部分小于temp，第二部分大于等于temp最后返回temp在A的下表+1的位置

int Partition(vector<int> &A,int begin,int &end)
{
end--;
int i = begin +1;
int temp = A[begin];
while(true)
{
while(true)
{
if(i<end&& A[i] <= temp)
++i;
else
break;
}
while(true)
{
if(A[end]>temp&& end>=0)
--end;
else
break;
}
if(i<end)
{
int v;
v =A[i];
A[i]=A[end];
A[end]=v;
}
else
return end;
}

}
int Select2( vector<int>& A,int begin,int end,int k)
{
int Acount = end - begin ;
int v = 0 ,temp1,temp;
if((end-begin)<=r)
{
insertsort(A,begin,end+1);
return (begin+k-1);
}
while(true)
{


for(int i =0; i!=Acount/r; ++i)
{
insertsort(A,begin+(i)*r,begin+(i+1)*r);
temp = A[begin+i];
A[begin+i] = A[begin+(i)*r+r/2];
A[begin+(i)*r+r/2] = temp;
}

if((Acount/r)%2 ==1)
v = Select2(A,begin,begin+Acount/r,(1+(Acount/r)/2));
else
v = Select2(A,begin,begin+Acount/r,(Acount/r)/2);
temp1 = A[begin];
A[begin] = A[v];
A[v] = temp1;
v = end;
Partition(A,begin,v);
if(k== (v-begin))
return v;
else if(k>v-begin)
{
k = k-(v - begin);
begin = v+1;
}
else
{
end = v;
}
}
}
int main()
{
vector<int> C;
C.push_back(10);
C.push_back(9);
C.push_back(8);
C.push_back(21);
C.push_back(11);
C.push_back(120);
C.push_back(94);
C.push_back(866);
C.push_back(2121);
C.push_back(1113);
C.push_back(10);
C.push_back(9);
C.push_back(8);
C.push_back(21);
C.push_back(11);
C.push_back(120);
C.push_back(94);
C.push_back(866);
C.push_back(2121);
C.push_back(1113);
C.push_back(10);
C.push_back(9);
C.push_back(8);
C.push_back(21);
C.push_back(11);
C.push_back(120);
C.push_back(94);
C.push_back(866);
C.push_back(2121);
C.push_back(1113);
C.push_back(10);
C.push_back(9);
C.push_back(8);
C.push_back(21);
C.push_back(11);
C.push_back(120);
C.push_back(94);
C.push_back(866);
C.push_back(2121);
C.push_back(1113);

cout<<Select2(C,2,C.size(),1)<<endl;
// int kk=4;
// Partition(C,3,kk);
// cout<<kk<<endl;
//// for(vector<int>::iterator iter=C.begin(); iter != C.end(); ++iter)
// {
// cout<<*iter<<endl;
// }

// vector<int> A ,Aa;
/* for(int i=0;i!=500 ; ++i)
{
A.push_back((int)rand());
Aa.push_back(A[i]);
}
insertsort(Aa,0,Aa.size());*/

/* for(int k=1;k!=A.size()+1;++k)
{ cout<<"第"<<k<<"小元素为：" ;
cout<<Select2(A,0,A.size(),k)<<"=="<<Aa[Select2(A,0,A.size(),k)]<<"?"<<"插入排序求第K小元素，验证上述算法结果."<<endl;
}*/
system("pause");
return 0;
}




有时间的话，帮忙调调这个吧，同样的，用二次取中求第K小元素的下标，内存泄漏搞不清楚。。。。