 |
快排 |
| □ 风炎 发表于 2007-2-12 5:08:00 |
＃i nclude<iostream>
using namespace std;
const int range=10000;
void swap(int *p,int *q)
{
int t;
t=*p;
*p=*q;
*q=t;
};
/*
交换有好多种实现，可是使用加减，或者是异或，这里只提供比较简单的使用第三变量的方法
stl中也提供了对交换操作的支持，但是不知道效率如何。
这里为了代码清晰一些，将交换写成了函数，实际使用时不如自己展开。
*/
int split_0 (int s[],int low,int high)
{
int i,j,x=s[low];
for (i=low,j=low+1;j<=high;++j)
{
if (x>s[j])
{
++i;
if (i!=j) swap(&s[i],&s[j]);
}
}
swap(&s[i],&s[low]);
return i;
}//这个是由一端到另一端比较大小的实现
void qsort(int s[],int low,int high)
{
int w;
//在每次调用之前可以随机化一下比较元素
w=split_0(s,low,high);
if (low<w-1) qsort(s,low,w-1);
if (w+1<high) qsort(s,w+1,high);
/*这里的比较操作也可以变为一个，即在调用split_0之前判断high和low。
但是需要进入下一层函数才能判断，不如分开写效率高*/
}
int main()
{
int i,n,s[range];
freopen("a.in","r",stdin);freopen("a.out","w",stdout);
cin>>n;
for (i=0;i<n;++i) cin>>s[i];
qsort(s,0,n-1);
cout<<n<<endl;
for (i=0;i<n;++i) cout<<s[i]<<endl;
return 0;
}
|
| □ 阅读全文 | 回复(2) | 引用通告 | 编辑 |
|
Re:快排 |
| □ Ranmocy(游客)发表评论于2007-11-11 19:10:00 |
 如果是100 0000个一样的数
好像怎么打都要递归100 0000层……
貌似会崩……
不知有没有人解释一下 |
| □ 个人主页 | 引用 | 返回 | 删除 | 回复 |
|
Re:快排 |
| □ qsort(游客)发表评论于2007-8-20 2:36:00 |
代码好烂，我贴一个。
void qsort(int *v, int l, int r)
{
int last,i;
if(l >= r)
return;
swap(v, l, (l+r)/2);
last = l;
for(i = l; i <= r; i++)
if(v[i] < v[l])
swap(v, ++last, i);
swap(v, l, last);
qsort(v, l, last-1);
qsort(v, last+1, r);
}
以下为blog主人的回复：
确实很烂，写的发泄而已。。。
献丑了... |
| □ 个人主页 | 引用 | 返回 | 删除 | 回复 |
| |
|
