[数据结构]——非比较排序—计数排序

该篇文章 所涉及代码收录仓库：登录 - Gitee.com

目录

1.非比较排序——计数排序

2.最终实现

1.解析

2.以int a[] = { 1,3,9,1,5,1,2,3,-5,-5,-2 };为例，手撕分析

3.代码实现

4.计数排序具有以下主要特性：

---

1.非比较排序——计数排序

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

2.最终实现

1.解析

2.以int a[] = { 1,3,9,1,5,1,2,3,-5,-5,-2 };为例，手撕分析

3.代码实现

void CountSort(int* a, int n)
{//找出最大和最小元素
	int min = a[0], max = a[0];
	for (int i = 1; i < n; i++)
	{
		if (a[i] < min)
			min = a[i];

		if (a[i] > max)
			max = a[i];
	}

	int range = max - min + 1;//确定新创建数组的数据个数和原数组大小相同，便于下面计数
	int* count = (int*)calloc(range, sizeof(int));
	if (count == NULL)
	{
		printf("calloc fail\n");
		return;
	}

	// 统计次数
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;//min作为偏移量，然后再在对应数组位置++，统计该数字出现的次数
	}

	// 排序
	int i = 0;
	for (int j = 0; j < range; j++)
	{
		while (count[j]--)
		{
			a[i++] = j + min;
		}
	}
}

4.计数排序具有以下主要特性：