计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序）
1. 算法步骤
1、找出待排序的数组中最大和最小的元素
2、统计数组中每个值为i的元素出现的次数，存入数组C的第i项
3、对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
4、反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
2. 动图演示
3. 时间复杂度
复杂度为Ο(n+k)（其中k是整数的范围）
4. 算法实现
计数排序C语言
#include<stdio.h>
#include<stdlib.h>
#define MAXNUM 10
void main()
{
void CountSort(int data[],int n);
int i,data[MAXNUM];
for(i=0;i<MAXNUM;i++)
scanf("%d",&data[i]);
CountSort(data,MAXNUM);
for(i=0;i<MAXNUM;i++)
printf("%d ",data[i]);
printf("\n");
}
void CountSort(int data[],int n)
{
int i,j,count,*data_p,temp;
data_p=(int*)malloc(sizeof(int)*n);
for(i=0;i<n;i++)//初始化data_p
data_p[i]=0;
for(i=0;i<n;i++)
{
count=0;
for(j=0;j<n;j++)//扫描待排序数组
if(data[j]<data[i])//统计比data[i]值小的值的个数
count++;
while(data_p[count]!=0)//对于相等非0的数据，应向后措一位。数据为0时，因数组data_p被初始化为0，故不受影响。
/* 注意此处应使用while循环进行判断，若用if条件则超过三个重复值后有0出现 */
count++;
data_p[count]=data[i];//存放到data_p中的对应位置
}
//用于检查当有多个数相同时的情况
i=0,j=n;
while(i<j)
{
if(data_p[i]==0)
{
temp=i-1;
data_p[i]=data_p[temp];
}//of if
i++;
}//of while
for(i=0;i<n;i++)//把排序完的数据复制到data中
data[i]=data_p[i];
free(data_p);//释放data_p
}
计数排序C++
#include <iostream>
using namespace std;
const int MAXN = 100000;
const int k = 1000; // range(范围)
int a[MAXN], c[MAXN], ranked[MAXN];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
++c[a[i]];
}
for (int i = 1; i < k; ++i)
c[i] += c[i-1];
for (int i = n-1; i >= 0; --i)
ranked[--c[a[i]]] = a[i];//如果是i表达的是原数标号，a[i]就是排序后的正确序列
for (int i = 0; i < n; ++i)
cout << ranked[i] << endl;
return 0;
}
计数排序PHP
function countingSort($arr, $maxValue = null)
{
if ($maxValue === null) {
$maxValue = max($arr);
}
for ($m = 0; $m < $maxValue + 1; $m++) {
$bucket[] = null;
}
$arrLen = count($arr);
for ($i = 0; $i < $arrLen; $i++) {
if (!array_key_exists($arr[$i], $bucket)) {
$bucket[$arr[$i]] = 0;
}
$bucket[$arr[$i]]++;
}
$sortedIndex = 0;
foreach ($bucket as $key => $len) {
if ($len !== null) $arr[$sortedIndex++] = $key;
if($len !== null){
for($j = 0; $j < $len; $j++){
$arr[$sortedIndex++] = $key;
}
}
}
return $arr;
}
计数排序JAVA
//针对c数组的大小，优化过的计数排序
publicclassCountSort{
publicstaticvoidmain(String[]args){
//排序的数组
int a[]={100,93,97,92,96,99,92,89,93,97,90,94,92,95};
int b[]=countSort(a);
for(inti:b){
System.out.print(i+"");
}
System.out.println();
}
public static int[] countSort(int[]a){
int b[] = new int[a.length];
int max = a[0],min = a[0];
for(int i:a){
if(i>max){
max=i;
}
if(i<min){
min=i;
}
}//这里k的大小是要排序的数组中，元素大小的极值差+1
int k=max-min+1;
int c[]=new int[k];
for(int i=0;i<a.length;++i){
c[a[i]-min]+=1;//优化过的地方，减小了数组c的大小
}
for(int i=1;i<c.length;++i){
c[i]=c[i]+c[i-1];
}
for(int i=a.length-1;i>=0;--i){
b[--c[a[i]-min]]=a[i];//按存取的方式取出c的元素
}
return b;
}
}
计数排序JavaScript
function countingSort(arr, maxValue) {
var bucket = new Array(maxValue+1),
sortedIndex = 0;
arrLen = arr.length,
bucketLen = maxValue + 1;
for (var i = 0; i < arrLen; i++) {
if (!bucket[arr[i]]) {
bucket[arr[i]] = 0;
}
bucket[arr[i]]++;
}
for (var j = 0; j < bucketLen; j++) {
while(bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}
计数排序C#语言
public int[] CountSort(int[] a)
{
int[] b = new int[a.Length];
int max = a[0];
int min = a[0];
foreach (int item in a)
{
if(item > max)
{
max = item;
}
else if (item < min)
{
min = item;
}
}
int k = max - min + 1;
int[] c = new int[k];
for (int i = 0; i < a.Length; i++)
{
c[a[i] - min] += 1;
}
for (int i = 1; i < c.Length; i++)
{
c[i] = c[i] + c[i - 1];
}
for (int i = a.Length-1; i >= 0; i--)
{
b[--c[a[i] - min]] = a[i];
}
return b;
}
计数排序Python
def count_sort(input_list): length = len(input_list) if length < 2: return input_list max_num = max(input_list) count = [0] * (max_num + 1) for element in input_list: count[element] += 1 output_list = [] for i in range(max_num + 1): for j in range(count[i]): # count[i]表示元素i出现的次数，如果有多次，通过循环重复追加 output_list.append(i) return output_list
计数排序Go语言
func countSort(arr []int) {
maxVal := 0
length := len(arr)
for i := 0; i < length; i ++ {
if arr[i] > maxVal {
maxVal = arr[i]
}
}
tmp := make([]int, maxVal+1)
for i := 0; i < length; i ++ {
tmp[arr[i]] += 1
}
j := 0
for i := 0; i < maxVal+1; i ++ {
for tmp[i] > 0 {
arr[j] = i
j ++
tmp[i] --
}
}
}
计数排序PASCAL
实现方法1：
program counting_sort1;
var
a,b,c:Array[1..max] of longint;
i,j,k,n:longint;
begin
readln(n);
for i:=1 to n do read(a[i]);
fillchar(c,sizeof(c),0);
for j:=1 to n do inc(c[a[j]]);
for i:=2 to x{x是大于a[i]中任意值的任意数且x≤max}do c[i]:=c[i]+c[i-1];
for j:=n downto 1 do
begin
b[c[a[j]]]:=a[j];
dec(c[a[j]]);
end;
for i:=1 to n do writeln(b[i],' ');
end.
实现方法2：
program counting_sort2;
const max=100;
var
a:array[1..max] of longint;
i,j,k,n,m,x:longint;
begin
readln(n);
fillchar(a,sizeof(a),0);//初始清空
m:=0;
for i:=1 to n do
begin
read(x);
inc(a[x]);
if x>m then m:=x;//找到最大的数
end;
for i:=1 to m do
if a[i]>0 then
for j:=1 to a[i] do
write(i,' ');
end.