{
作者：时光9154
当然底下的C代码是我(Comzyh)写的
http://hi.baidu.com/time9154
}
多关键字的快速排序
解决类似如下的问题：输入n组坐标（xi，yi），要求按xi的升序排序后，对于xi=xj（j>i），yi~j升序排列
即双关键字排序，先保证第一关键字的升序，在第一关键字一样的情况下保证第二关键字的升序
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
var a:array[0..maxn,1..2]of longint; n,i:longint; procedure qsort(v1,v1:longint); var i,j,mid1,mid2,temp:longint; begin i:=v1; j:=v2; mid1:=a[(i+j) shr 1,1]; mid2:=a[(i+j) shr 1,2]; while i<j do begin while (a[i,1]<mid1) or ((a[i,1]=mid1) and (a[i,2]<mid2)) do inc(i); while (a[j,1]>mid1) or ((a[j,1]=mid1) and (a[j,2]>mid2)) do dec(j); if i<=j then begin temp:=a[i,1]; a[i,1]:=a[j,1]; a[j,1]:=temp; temp:=a[i,2]; a[i,2]:=a[j,2]; a[j,2]:=temp; inc(i); dec(j); end; end; if v1<j then qsort(v1,j); if i<v2 then qsort(i,v2); end; |
多关键字的排序可以一次类推，比如再加一个第三关键字Zi（保证降序）
即改为
|
1 2 3 |
while (a[i,1]<mid1) or ((a[i,1]=mid1) and (a[i,2]<mid2)) or((a[i,1]=mid1) and (a[i,2]=mid2) and (a[i,3]>mid3)) do inc(i); while (a[j,1]>mid1) or ((a[j,1]=mid1) and (a[j,2]>mid2)) or((a[j,1]=mid1) and (a[j,2]=mid2) and (a[j,3]<mid3)) do dec(j); |
下面给一段Comzyh的C++版本
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
/* Program:双关键字快速排序演示程序 Author:Comzyh */ #include <cstdio> #include <cstdlib> struct data { int a,b;//双关键字 }; data tab[1000],y;//y:交换变量 int N; void qsort(int b,int e); int main() { int i; printf("Please Enter number of cases:"); scanf("%d",&N); for (i=1;i<=N;i++) scanf("%d%d",&tab[i].a,&tab[i].b); qsort(1,N); printf("Sorting...\n"); for (i=1;i<=N;i++) printf("%4d %4d\n",tab[i].a,tab[i].b); system("pause"); } void qsort(int b,int e) { int i=b,j=e; data x=tab[(b+e)>>1]; while (i<j) { //这里是改过的比较语句 while (tab[i].a<x.a ||((tab[i].a ==x.a) && (tab[i].b<x.b)))i++; while (tab[j].a>x.a ||((tab[j].a ==x.a) && (tab[j].b>x.b)))j--; if (i<=j) { y=tab[i]; tab[i]=tab[j]; tab[j]=y; i++;j--; } } if (b<j)qsort(b,j); if (i<e)qsort(i,e); } |