计数排序

基本思想

如果对一定范围内的整数排序，可以使用计数排序。算法思想是对于每个元素x，记录小于或等于它的元素的个数。令k为元素最大值，n为元素个数。

算法实现

Function Countingsort(n:longint;s:arraytype):arraytype;
Var 
   i:longint;
   c:array[0..k] of longint;
Begin{s为输入数据，c[i]为小于等于i的元素的个数}
   fillchar(c,sizeof(c),0);
   for i:=1 to n do inc(c[s[i]]);
   for i:=1 to k do inc(c[i],c[i-1]);
   for i:=n downto 1 do begin
      countingsort[c[s[i]]]:=s[i];
      dec(c[s[i]]);
   end;
End;

算法实例

例：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[i]);
 for i:=1 to m do c[i]:=0;
 for i:=1 to n do c[a[i]]:=c[a[i]]+1;
 for i:=2 to m do c[i]:=c[i]+c[i-1];
 for i:=n downto 1 do
  begin
  b[c[a[i]]]:=a[i];
  c[a[i]]:=c[a[i]]-1;
 end;
 writeln('Sorted data:');
 for i:= 1 to n do
  write(b[i]:6);
end.

计数排序是一个小作品，欢迎帮助扩充这个条目。