计数排序

---

标题：计数排序

---

计数排序基本思想：计数排序（Counting Sort）又称为鸽巢原理，是对哈希直接定制法变形应用，是一种稳定的算法，它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法，当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(nlog(n))，如归并排序，堆排序）

---

操作步骤：

• 统计相同元素出现的次数
• 根据统计的结果将序列回收到原来的序列中
  

---

代码实现如下：

 #include<stdio.h>
 #include<assert.h>
 #include<stdlib.h>
//计数排序
void CountSort(int *a, int len)
{
	assert(a);
	//通过max和min计算出临时数组所需要开辟的空间大小
	int max = a[0], min = a[0];
	for (int i = 0; i < len; i++){
		if (a[i] > max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
	}
	//使用calloc将数组都初始化为0
	int range = max - min + 1;
	int *b = (int *)calloc(range, sizeof(int));
	//使用临时数组记录原始数组中每个数的个数
	for (int i = 0; i < len; i++){
		//注意：这里在存储上要在原始数组数值上减去min才不会出现越界问题
		b[a[i] - min] += 1;
	}
	int j = 0;
	//根据统计结果，重新对元素进行回收
	for (int i = 0; i < range; i++){
		while (b[i]--){
			//注意：要将i的值加上min才能还原到原始数据
			a[j++] = i + min;
		}
	}
	//释放临时数组
	free(b);
	b = NULL;
}
//打印数组
void PrintArray(int *a, int len)
{
	for (int i = 0; i < len; i++){
		printf("%d ", a[i]);
	}
	printf("\n");
}
int main()
{
	int a[] = { 3, 4, 3, 2, 1, 2, 6, 5, 4, 7 };
	printf("排序前：");
	PrintArray(a, sizeof(a) / sizeof(int));
	CountSort(a, sizeof(a) / sizeof(int));
	printf("排序后：");
	PrintArray(a, sizeof(a) / sizeof(int));
	system("pause");
	return 0;
}

调试结果如下：