countingsort.h

来自「快速排序、合并排序、插入排序、堆排序、计数排序等算法的C语言实现」· C头文件 代码 · 共 27 行

#include<stdio.h>
//问题：n个可以相同的整数A[1..n]，1≤A[i]≤k，i=1~n，这里k是A[i]的取值范围，不一定为n。
//基本思想：
//步骤：A[1..n]→计数器C[1..k]→B[1..n]
//Step 1(值相同元素的计数)：将A中的值为i的元素个数记入C[i]中；
//Step 2(累计计数)：对C[1..k]进行修改，使得C[i]的值表示为≤i的元素个数；
//Step 3(放置)：将A[j]依据C[A[j]]，放入正确位置B[C[A[j]]]上，并修改C[A[j]] ←C[A[j]]-1；
#define MaxA 30//MaxA为数组A的最大元素值
typedef int ElemType;

void CountingSort(ElemType A[],ElemType B[],long LengthA)
{//计算排序
	long i,j;
	ElemType C[MaxA+1];
	for(i=0;i<=MaxA;i++)
		C[i]=0;
	for(j=0;j<LengthA;j++)
		C[A[j]]++;
	for(i=1;i<=MaxA;i++)
		C[i]=C[i]+C[i-1];
	for(j=LengthA-1;j>=0;j--)
	{
		B[C[A[j]]-1]=A[j];
		C[A[j]]--;
	}

}