🍵计数排序基本思想及其代码实现

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤： 统计相同元素出现次数 根据统计的结果将序列回收到原来的序列中

🍷图解 最后根据每个数字出现的次数将其拷回原数组就行 🍹代码实现

void CountSort(int* a, int n)
{
          
   
	int max = a[0], min = a[0];
	for (int i = 1; i < n; ++i)
	{
          
   
		if (a[i] > max)
		{
          
   
			max = a[i];
		}

		if (a[i] < min)
		{
          
   
			min = a[i];
		}
	}

	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int)*range);
	if (count == NULL)
	{
          
   
		printf("malloc fail
");
		exit(-1);
	}
	// 统计次数
	for (int i = 0; i < n; ++i)
	{
          
   
		count[a[i] - min]++;
	}

	// 根据次数，进行排序
	int j = 0;
	for (int i = 0; i < range; ++i)
	{
          
   
		while (count[i]--)
		{
          
   
			a[j++] = i + min;
		}
	}
}

🧋排序总结

🍸稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且r[i]在r[j]之前，则称这种排序算法是稳定的，否则称为不稳定。

简单来说就是排序之后相对位置是否发生变化。 例如， 2 1 4 3 2’ 6 7 排完序后 1 2 2’ 3 4 6 7 2原来就在2’前面，排完序后还是在前面就说明这个排序是稳定的，如果排完序后2在2’后面就说明这个排序是不稳定的。