线形排序 以上我们讨论的算法均是基于比较的排序算法,在排序算法中有基于数字本身的算法:计数、桶、基数排序。 1.计数排序 基本思想是对于序列中的每一元素x,确定序列中小于x的元素的个数。 例:n个整数序列且每个值在[1,m],排序之。 program jspx;
const m=6;n=8;
var i,j:integer;
a,b:array[1..n] of integer;
c:array[1..m] of integer;
begin
writeln('Enter data:');
for i:=1 to n do read(a);
for i:=1 to m do c:=0;
for i:=1 to n do c[a]:=c[a]+1;
for i:=2 to m do c:=c+c[i-1];
for i:=n downto 1 do
begin
b[c[a]]:=a;
c[a]:=c[a]-1;
end;
writeln('Sorted data:');
for i:= 1 to n do
write(b:6);
end. 2.桶排序 桶排序的思想是若待排序的记录的关键字在一个明显有限范围内(整型)时,可设计有限个有序桶,每个桶装入一个值,顺序输出各桶的值,将得到有序的序列。 例:输入n个0到100之间的整数,由小到大排序输出。 program tpx;
const n=7;
var b:array[0..100] of integer;
k:0..100;
i:integer;
begin
write('Enter date ![](static/image/smiley/default/sad.gif) 0-100)');
for i:=0 to 100 do b :=0;
for i:= 1 to n do
begin
read(k);
b[k]:=b[k]+1;
end;
writeln('Output data:');
for i:=0 to 100 do
while b>0 do begin write(i:6);b:=b-1 end;
writeln;
end.3.基数排序 基本思想是对n个元素依次按k,k-1,...1位上的数字进行桶排序。 program jspx;
const n=8;
type link=^node;
node=record
data:integer;
next:link;
end;
var i,j,l,m,k:integer;
a:array[1..n] of integer;
s:string;
q,head:array[0..9] of link;
p,p1:link;
begin
writeln('Enter data:');
for i:=1 to n do read(a);
for i:=5 downto 1 do
begin
for j:=0 to 9 do
begin
new(head[j]);
head[j]^.next:=nil;
q[j]:=head[j]
end;
for j:=1 to n do
begin
str(a[j],s);
for k:=1 to 5-length(s) do
s:='0'+ s;
m:=ord(s)-48;
new(p);
p^.data:=a[j];
p^.next:=nil;
q[m]^.next:=p;
q[m]:=p;
end;
l:=0;
for j:=0 to 9 do
begin
p:=head[j];
while p^.next<>nil do
begin
l:=l+1;p1:=p;p:=p^.next;dispose(p1);a[l]:=p^.data;
end;
end;
end;
writeln('Sorted data:');
for i:= 1 to n do
write(a:6);
end.
|