计数排序算法描述
2026-02-09 13:51:11
计数排序算法是一种简单直观的排序方法，适用于整数范围较窄的情况。它的基本思想是统计每个输入元素出现的次数，然后根据这些计数重构排序后的序列。以下是使用Pascal语言的实现:
pascal
var
i, j, n: longint;
a, b: array[0..1000] of longint;
begin
read(n);
for i := 1 to n do
begin
read(a[i]);
b[a[i]] := b[a[i]] + 1;
end;
for i := 0 to 1000 do
if b[i] > 0 then
for j := 1 to b[i] do
write(i, ' '); // 输出部分
end.
另一个例子是使用Pascal实现对n个整数（范围在[1, m]）进行计数排序:
pascal
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.
在其他编程语言中，如JavaScript，计数排序的实现可以这样表示:
`counting_sort = function(array, k) {
array_sorted = {};
count = {};
for (i = 0; i < k; i++) {
count[i] = 0;
}
for (i = 1; i <= array.length; i++) {
count[array[i]] = count[array[i]] + 1;
}
// 统计位置
for (i = 1; i <= k; i++) {
count[i] += count[i - 1];
}
// 重构排序序列
for (i = array.length - 1; i >= 0; i--) {
n = array[i];
array_sorted[count[n]] = n;
count[n]--;
}
return array_sorted;
};
// 示例使用
array = [12, 3, 22, 7, 6, 23, 26];
max = Math.max(...array);
array = counting_sort(array, max);
// 输出排序后的结果
for (i = 1; i <= array.length; i++) {
console.log(array[i]);
}
扩展资料
算法介绍
热门标签
