【算法】- 排序 - 计数排序

---

前言

编译语言：c++
编译器：VS2022

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、计数排序思想

计数排序，就是创建一个数组，数组下标即为排序的数，我们把要排序数组的数通过记录出现的次数，再通过计数的数组，打印下标，这样就可以排好序了。

二、计数排序

int* CountSort(int arr[],int carr[])
{
int i;
for (i = 1; i <= MAXSIZE; i++)
{
carr[arr[i]] = carr[arr[i]] + 1;
}
return carr;
}
int main()
{
int i,j;
int carr[MAXSIZE + 1] = { 0 };
int arr[MAXSIZE + 1] = { 0,2,3,8,7,1,2,2,2,7,3,9,8,2,1,4,2,4,6,9,2 };
CountSort(arr,carr);

for (i = 1; i <= MAXSIZE; i++)
{
j = carr[i];
while (j)
{
cout << i << " ";
j--;
}
}
return 0;
}

三、计数排序优化

通过以上基数排序会发现一个问题，如果我们只排序{101,105,106,102,109,108,103,104}这样的数列，难道我们要临时创建一个大小为110的数组吗？显然这样会造成大量空间的浪费。那我们该怎么做呢？
其实我们可以临时创建一个max-min+1大小的数组，记录数组中的最大值和最小值，在我们计数时通过数值减去一个偏量（也就是最小值）就可以计数了，在我们开始排序时通过下标加上偏量这样就可以完成排序

//计数排序

int* CountSort(int arr[],int n)
{
int i,j;
int max = 0;
int min = 9999;
for (i = 1; i <= MAXSIZE; i++)//找到数组中的最大值和最小值
{
if (arr[i] > max)
max = arr[i];
if (arr[i] < min)
min = arr[i];
}
int carr[max - min + 1] = {0};//创建max-min+1大小的数组，从下标1开始计数
for (i = 1; i <= MAXSIZE; i++)
{
carr[arr[i]-min] = carr[arr[i]-min] + 1;//进行计数
}

for (i = 1; i <= MAXSIZE; i++)
{
j = carr[i];
while (j)
{
cout << i + min << " ";
j--;
}
}
}

int main()
{
int i,j;
int* carr;
//int carr[MAXSIZE + 1] = { 0 };
int arr[MAXSIZE + 1] = { 0,102,103,108,107,101,102,102,102,107,103,109,108,102,101,104,102,104,106,109,102 };
CountSort(arr,MAXSIZE);//计数排序传入数组和长度
return 0;
}

这里由于vs2022不支持C99,所以并不能实现变长数组，所以会在VS2022编译器中报错，但思想也就是这样。

---

总结

计数排序需要满足的条件：
排序的元素必须时整数
排序元素要在一定的范围内，并且比较集中。这样才能最大发挥计数排序的优势
时间复杂度为：O(n+k)

原文地址：https://blog.csdn.net/2302_77182146/article/details/142703267

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！