本篇内容介绍了“C++中如何实现计数排序”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
计数排序
计数排序是一种非比较的排序算法
优势：
计数排序在对于一定范围内的整数排序时，时间复杂度为O(N+K) （K为整数在范围）快于任何比较排序算法，因为基于比较的排序时间复杂度在理论上的上下限是O(N*log(N))。
缺点：
计数排序是一种牺牲空间换取时间的做法，并且当K足够大时O（K）>O(N*log(N)),效率反而不如比较的排序算法。并且只能用于对无符号整形排序。
时间复杂度：
O（N） K足够大时为O（K）
空间复杂度：
O（最大数-最小数）
性能：
计数排序是一种稳定排序
代码实现：
计算
安全
数据库
网络和加速
企业服务
#include <iostream>
#include <Windows.h>
#include <assert.h>
using namespace std;
//计数排序，适用于无符号整形
void CountSort(int* a, size_t size)
{
assert(a);
size_t max = a[0];
size_t min = a[0];
for (size_t i = 0; i < size; ++i)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
size_t range = max - min + 1; //要开辟的数组范围
size_t* count = new size_t[range];
memset(count, 0, sizeof(size_t)*range); //初始化为0
//统计每个数出现的次数
for (size_t i = 0; i < size; ++i) //从原数组中取数，原数组个数为size
{
count[a[i]-min]++;
}
//写回到原数组
size_t index = 0;
for (size_t i = 0; i < range; ++i) //从开辟的数组中读取，开辟的数组大小为range
{
while (count[i]--)
{
a[index++] = i + min;
}
}
delete[] count;
}
void Print(int* a, size_t size)
{
for (size_t i = 0; i < size; ++i)
{
cout << a[i] << " ";
}
cout << endl;
}#include "CountSort.h"
void TestCountSort()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 2, 2, 2, 4, 5, 8, 9, 5, 11, 11, 22, 12, 12 };
size_t size = sizeof(arr) / sizeof(arr[0]);
CountSort(arr, size);
Print(arr, size);
}
int main()
{
TestCountSort();
system("pause");
return 0;
}“C++中如何实现计数排序”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://www.xuebuyuan.com/3289602.html
