void swap(int& a, int& b)
{
int c = a;
a = b;
b = c;
}
int partion(int a[], int p, int r)
{
double pp = rand()/double(RAND_MAX);
int randpos = (int)((r-p) * pp) + p;
swap(a[p], a[randpos]);
int x = a[p];
int i=0, j =0;
i = p, j = r +1;
while(1)
{
while (i <r &&a[++i] < x);
while (a[--j] > x);
if (i >= j)
{
break;
}
swap(a[i],a[j]);
}
a[p] = a[j];
a[j] = x;
return j;
}
int main()
{
int a[] = {7,6,5,1};
int pos = 0;
int K = 9994;
int st = 0;
int ed = sizeof (a) /sizeof(a[0]) - 1;
while (K)
{
pos = partion(a, st, ed);
if (ed - pos +1 <= K)
{
K -= ed-pos + 1;
for (int j = pos; j <= ed; ++j)
cout << a[j] << endl;
ed = pos - 1;
}
else
{
st = pos+1;
}
if (st > ed)
{
cout << "error " << endl;
return 1;
}
}
return 0;
}
posted on 2010-04-28 23:09
RUI 阅读(446)
评论(0) 编辑 收藏 引用