非比较排序

发布时间：2024年01月17日
思想：计数排序又称为 鸽巢原理 ，是对 哈希直接定址法的变形应用 。 操作步骤：
1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中
先统计出现次数（如下）
找出最大值和最小值（ 以免浪费开辟的空间 ）： 
    int max, min;
	max = min = a[0];
	for (i = 0; i < n; i++)
	{
		if (a[i] > max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
	}

接着就可以求出所要开辟的空间的大小：

    int range = max - min + 1;
	int* tmp = (int*)calloc(range, sizeof(a[i]));

接着进行计数统计：

    for (i = 0; i < n; i++)
	{
		tmp[a[i]]++;
	}
计数数组的下标即为原数组中的元素。
统计完成后，再根据循环依次打印到原数组： 
    for (i = 0; i < range; i++)
	{
		while (tmp[i]--)
		{
			a[j] = i + min;
			j++;
		}
	}

完整代码：

void CountSort(int* a, int n)
{
?? ?int i = 0;
?? ?int j = 0;
?? ?int max, min;
?? ?max = min = a[0];
?? ?for (i = 0; i < n; i++)
?? ?{
?? ??? ?if (a[i] > max)
?? ??? ??? ?max = a[i];
?? ??? ?if (a[i] < min)
?? ??? ??? ?min = a[i];
?? ?}
?? ?int range = max - min + 1;
?? ?int* tmp = (int*)calloc(range, sizeof(a[i]));
?? ?for (i = 0; i < n; i++)
?? ?{
?? ??? ?tmp[a[i]]++;
?? ?}
?? ?for (i = 0; i < range; i++)
?? ?{
?? ??? ?while (tmp[i]--)
?? ??? ?{
?? ??? ??? ?a[j] = i + min;
?? ??? ??? ?j++;
?? ??? ?}
?? ?}
}

对于衔接比较紧密的数中（即每个数的间隔不会很大）的时候，这类非比较的效率也是非常的高

时间复杂度：O（max（n，range））。

文章来源:https://blog.csdn.net/cy18779588218/article/details/135645361
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章