编辑

哈喽大家好，我是保护小周ღ，本期为大家带来的是排序算法中的计数排序，非常的有意思，值得学习而且计数排序是非交换排序，分享所有源代码，粘贴即可运行，保姆级讲述，包您一看就会，快来试试吧~

编辑

目录

一、计数排序

1.1 算法思想

1.2 程序设计

1.3 程序实现

1.4 计数排序总结

一、计数排序

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。[1] 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序）                                                                                                                    

                                                                                                                                    ——百度百科

1.1 算法思想：

编辑

其实会发现一个主要问题，那么就是tmp数组（使用动态开辟）到底应该开辟多大的空间，怎么计算。

假设我们有组数据，100  101   102   101  109  105    105；

我们应该开辟多大的空间，因为最大值是109，从0开始需要开辟110个空间吗？那太浪费了。

编辑

所以我们只需要最大值-最小值+1的空间，max=109,min=100 , max-min+1=10；使用相对映射的位置。

编辑

1.2 程序设计

第一步：

我们自定义一个函数CountSort();将计数排序的功能实现一下，参数有数组a的地址（我们用指针接收，数组名其实就是地址），另一个参数是：计算数组a里有多少个元素，标准操作为：

sizeof ( a ) / sizeof ( a[ 0 ] );

第二步：

我们要在函数内部计算数组a里元素的最大值和最小值（遍历），然后求出数据的范围 range=max - min +1;

第三步：

定义动态开辟的数组tmp,因为我已经得到数据有多少，我们就可以开辟了。

但是我们又想要将tmp数组里的值初始化为0；

博主的方式是直接使用calloc();开辟，calloc() 与 malloc() 函数是一样的功能，只是 calloc() 的函数参数表达方式略有不同，其次是它会将动态开辟的空间值初始化为0；

还有一种方法是使用 memset()函数，menset(tmp,  0 , sizeof( int ) * range );这几个参数应该能理解吧？

只要是动态开辟的空间，我们用完之后一定要随手将它释放掉，就像打括号 { } 一样，可以先写着，避免遗忘。将free（tmp）；放到代码最后即可。

第四步：

统计数组a里的每个元素出现的次数，然后映射至tmp数组。（使用相对映射）；

第五步：

将tmp数组里不为0的元素的下标+min反赋给数组a,遍历结束，排序完成。

1.3 程序实现：

#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>voidCountSort(int*a, intn)
{
intmax=a[0];
intmin=a[0];
for (inti=0; i<n; ++i)//遍历找打最大值和最小值    {
if (a[i] >max)
        {
max=a[i];
        }
if (a[i] <min)
        {
min=a[i];
        }
    }
intrange=max-min+1;//计算范围int*tmp= (int*)calloc(range, sizeof(int));//动态开辟if (tmp==NULL)//如果空间申请失败，报个错，并中止程序    {
perror("calloc");
return;
    }
for (inti=0; i<n; ++i)//统计数组a每个元素出现的次数    {
tmp[a[i] -min]++;
    }
intj=0;
for (inti=0;i<range;++i)//    {
while (tmp[i])//判断tmp数组该元素是否有计数。        {
a[j++] =i+min;//如果有就把该元素的下标值反映射至数组atmp[i]--;
        }
    }
//动态开辟的空间，主动释放free(tmp);
tmp=NULL;
}
//打印voidPrint(int*a,intn)
{
for (inti=0;i<n;++i)
    {
printf("%d ",a[i]);
    }
}
intmain()
{
inta[] = {-1,1,2,9,8,8,1,3,4,3,4,5};
CountSort(a, sizeof(a) /sizeof(a[0]));//计数排序Print(a, sizeof(a) /sizeof(a[0]));//打印return0;
}

编辑

1.4 计数排序总结

计数排序：思想很巧妙，适用范围具有局限性(整型数据)

时间复杂度：O(N+range);非常块，但是数据范围很大的就差些，说明它适用于范围集中一组整型数据排序。

空间复杂度：O(range);

至此计数排序的算法思想博主已经分享完了，相信大家对这个逻辑有了一定的理解，大家可以自己动手敲敲代码，感受一下。

编辑

本期收录于博主的专栏——排序算法，适用于编程初学者，感兴趣的朋友们可以订阅，查看其它“常见排序”。 排序算法_保护小周ღ的博客-CSDN博客

感谢每一个观看本篇文章的朋友，更多精彩敬请期待：保护小周ღ  *★,°*:.☆(￣▽￣)/$:*.°★*  

文章存在借鉴，如有侵权请联系修改删除！ 编辑