线形排序

线形排序

以上我们讨论的算法均是基于比较的排序算法，在排序算法中有基于数字本身的算法：计数、桶、基数排序。

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 date0-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.