返回信息流#include<iostream>
using namespace std;
void Swap(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
}
void quicksort(int arr[],int l,int r)
{
if(l>=r) return;
if(l<r)
{
int i=l;
int j=r;
int pviot=arr[l];
while(i<j)
{
while(i<j&&arr[j]>=pviot) j--;
if(i<j) arr[i]=arr[j];
while(i<j&&arr[i]<=pviot) i++;
if(i<j) arr[j]=arr[i];
}
arr[i]=pviot;
quicksort(arr,l,i-1);
quicksort(arr,i+1,r);
}
}
int main()
{
int a[]={8,4,5,1,10,77,0};
quicksort(a,0,sizeof(a)/sizeof(int)-1);
for(int i=0;i<sizeof(a)/sizeof(int);i++)
cout<<a[i]<<" ";
}
——————————————————————————————————————————————
#include<iostream>
using namespace std;
void Swap(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
}
void quicksort(int arr[],int l,int r)
{
if(l>=r) return;
if(l<r)
{
int i=l;
int pviot=arr[l];
for(int j=l;j<=r;j++)
{
if(arr[j]<pviot)
{
i++;
if(i!=j)
Swap(arr[i],arr[j]);
}
}
Swap(arr[i],arr[l]);
quicksort(arr,l,i-1);
quicksort(arr,i+1,r);
}
}
int main()
{
int a[]={8,4,5,1,10,77,0,5,10,0,-10,-10};
quicksort(a,0,sizeof(a)/sizeof(int)-1);
for(int i=0;i<sizeof(a)/sizeof(int);i++)
cout<<a[i]<<" ";
}
——————————————————————————————————————————
两种方式都可以，但是这两种哪一种更好呢，还是这两种一样
这是一条镜像帖。来源：北邮人论坛 / cpp / #94926同步于 2017/3/22
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
更：手写快排问题
bingge
2017/3/22镜像同步9 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
确实写错了，改后依然无法处理重复元素的问题
【 在 jiarong 的大作中提到: 】
: while(i<j&&arr[j]>=pviot) j--;
: if(i<j) arr[l]=arr[j];
: 你这里写错了。arr[i]=arr[j]
wikipedia Lomuto partition vs Hoare partition. Lomuto hits worst case when elements are all the same but Hoare doesn't. Your first version isn't standard Hoare because you keep advancing the pointer when the element equals the pivot. This won't always partition the array in the middle in case where all elements are the same, unless you change arr[j]>=pviot to arr[j]>pviot and arr[i]<=pviot to arr[i]<pviot
sorry，my English is poor.
if i change arr[j]>=pviot to arr[j]>pviot and arr[i]<=pviot to arr[i]<pviot,the program does not work well.But,if I only change one of the expression,it will work well as the original one.
【 在 GentlyGuitar 的大作中提到: 】
: wikipedia Lomuto partition vs Hoare partition. Lomuto hits worst case when elements are all the same but Hoare doesn't. Your first version isn't standard Hoare because you keep advancing the pointer when the element equals the pivot. This won't always partition the array in the middle in case where all elements are the same, unless you change arr[j]>=pviot to arr[j]>pviot and arr[i]<=pviot to arr[i]<pviot
【 在 bingge 的大作中提到: 】
: sorry，my English is poor.
: if i change arr[j]>=pviot to arr[j]>pviot and arr[i]<=pviot to arr[i]<pviot,the program does not work well.But,if I only change one of the expression,it will work well as the original one.
上次用的那个电脑上没有中文输入法。。
我想说的是这个伪代码：
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p)
quicksort(A, p + 1, hi)
algorithm partition(A, lo, hi) is
pivot := A[lo]
i := lo - 1
j := hi + 1
loop forever
do
i := i + 1
while A[i] < pivot
do
j := j - 1
while A[j] > pivot
if i >= j then
return j
swap A[i] with A[j]
在实践中hoare确实比lomuto（也就是你第二个版本）更快。当所有元素相同的时候，hoare依然会挨个交换，最后头尾两个指针逼近到中央相会，就避免了分割点在两端的情况。
啥惊喜，百度了白天，就知道markdown是个可以自己排版的东西，并不知道怎么用
【 在 Silencecjx 的大作中提到: 】
: 试试用markdown贴代码吧，有惊喜