基数排序如何实现?(Pascal语言)
发布网友
共2个回答
热心网友
拜托，基数排序不是多关键字排序。
以下是快排的多关键字排序：
program qsort_hwr;
const
maxn=1000000;
var
a:array[0..maxn,1..2]of longint;
n,i:longint;
procere qsort(x,y:longint);
var
i,j,m1,m2:longint;
begin
i:=x;
j:=y;
m1:=a[(x+y) shr 1,1];
m2:=a[(x+y) shr 1,2];
repeat
while (a[i,1]<m1)or((a[i,1]=m1)and(a[i,2]<m2)) do inc(i);
while (a[j,1]>m1)or((a[j,1]=m1)and(a[j,2]>m2)) do dec(j);
if i<=j then begin
a[0]:=a[i];
a[i]:=a[j];
a[j]:=a[0];
inc(i);
dec(j);
end;
until i>j;
if x<j then qsort(x,j);
if i<y then qsort(i,y);
end;
begin
while not eof do begin
readln(n);
for i:=1 to n do readln(a[i,1],a[i,2]);
qsort(1,n);
writeln;
for i:=1 to n do writeln(a[i,1],' ',a[i,2]);
end;
end.
比如说，要把N个1~100的数排序，我们就设立一个a数组，a[i]表示数字i出现的次数，这样就可以排好序，但基数排序是不稳定的，因为如果有两个数1，1000，那么冒泡排序需要做2次比较，但基数排序需要运行1000趟。
下面是程序：
var
a:array[0..100]of longint;
min,max,n,i,tmp:longint;
begin
fillchar(a,sizeof(a),0);
min:=maxlongint;
max:=-min;//max和min是数字的最大和最小边界。
readln(n);
for i:=1 to n do begin
read(tmp);
inc(a[tmp]);//tmp的出现次数+1
if tmp>max then max:=tmp;
if tmp<min then min:=tmp;
end;
for i:=min to max do
while a[i]<>0 do begin//如果i这个数字还没有打印完，就继续打印
dec(a[i]);//把i打印并且次数-1.
write(i,' ');
end;
writeln;
end.
热心网友
“基数排序法”（radix sort）则是属于“分配式排序”（distribution sort），基数排序法又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。
解法
基数排序的方式可以采用LSD（Least sgnificant digital）或MSD（Most sgnificant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
var
a:array[0..100]of longint;
min,max,n,i,tmp:longint;
begin
fillchar(a,sizeof(a),0);
min:=maxlongint;
max:=-min;//max和min是数字的最大和最小边界。
readln(n);
for i:=1 to n do begin
read(tmp);
inc(a[tmp]);//tmp的出现次数+1
if tmp>max then max:=tmp;
if tmp<min then min:=tmp;
end;
for i:=min to max do
while a<>0 do begin//如果i这个数字还没有打印完，就继续打印
dec(a);//把i打印并且次数-1.
write(i,' ');
end;
writeln;
end.
