快排 快速排序 qsort quicksort C语言

现在网上搜到的快排和我以前打的不太一样,感觉有点复杂,我用的快排是FreePascal里/demo/text/qsort.pp的风格,感觉特别简洁。

 #include<stdio.h>
#define MAXN 10000
int a[MAXN];
int n;
void Mysort(int l, int r) {
int x,y,mid,t;
mid = a[(l+r)/];
x=l;
y=r;
do {
while(a[x]<mid)x++;
while(a[y]>mid)y--;
if(x<=y) {
t=a[x];
a[x]=a[y];
a[y]=t;
x++;
y--;
}
} while(x<=y);
if(l<y)Mysort(l,y);
if(x<r)Mysort(x,r);
}
int main() {
int i;
scanf("%d",&n);
for(i=; i<n; i++) {
scanf("%d",&a[i]);
}
Mysort(,n-);
for(i=; i<n; i++)printf("%d ",a[i]);
return ;
}

(其中(x+y)/2可以写成(x+y)>>1提升速度

(最近要实习生面试了,复习一下基础算法。之前排序基本都用STL的sort了,快排都快忘了,没想到我还是一遍就打出来了蛤铪哈)

更新一下:

算导快排:

 int mypartition(int a[], int lo, int hi){
int pivot = a[hi];
int i = lo;
for(int j=lo; j<hi; j++){
if(a[j]<=pivot){
swap(a[i],a[j]);
i++;
}
}
swap(a[i],a[hi]);
return i;
} void mysort(int a[], int lo, int hi){
if(lo>=hi)return;
int i = mypartition(a, lo, hi);
mysort(a, lo, i-);
mysort(a, i+, hi);
}

另一种快排,和最上面那个差不多,据说算导的swap次数太多,效率不如这种。这个是hdu1425代码

 #include<cstdio>
#include<algorithm>
using namespace std; int a[]; int mypartition(int a[], int lo, int hi) {
int p = a[lo];
int i=lo-;
int j=hi+;
while(true) {
do {
i++;
} while(a[i]<p);
do {
j--;
} while(a[j]>p);
if(i>=j)return j;
swap(a[i],a[j]);
}
} void mysort(int a[], int lo, int hi) {
if(lo>=hi)return;
int i = mypartition(a, lo, hi);
mysort(a, lo, i);
mysort(a, i+, hi);
} int main() {
int n,m;
while(scanf("%d%d",&n,&m)!=EOF) {
for(int i=; i<n; i++) scanf("%d",&a[i]);
mysort(a,,n-);
if(m>)printf("%d",a[n-]);
for(int i=; i<m; i++) {
printf(" %d",a[n--i]);
}
puts("");
}
return ;
}
上一篇:AC日记——Maximal GCD codeforces 803c


下一篇:codeforces 798 C. Mike and gcd problem(贪心+思维+数论)