计数排序

提示：这里可以添加系列文章的所有文章的目录，目录需要自己手动添加 例如：第一章 Python 机器学习入门之pandas的使用

---

提示：写完文章后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

计数排序一、什么是计数排序？二、算法思想三、代码四、局限性

一、什么是计数排序？

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

二、算法思想

通俗讲，就是利用额外空间将数组中每个元素进行次数统计，再将统计后的结果按统计数组下标和统计次数复原原数组，得到排序结果 1.遍历整个数组，找出数组范围（找到最大值） 2.建立和数组范围一样大的统计数组，将每个数字放入对应的统计数组中 3.遍历统计数组，输出结果

三、代码

int* countSort(int *arrary, int len) { //1.得到数列的最大值 int max = INT_MIN; for (int i = 0; i < len; ++i) { if (arrary[i] > max) { max = arrary[i]; } } //2.根据数列的最大值获取统计数组的长度 int* countArrary = new int[max + 1]; for (int i = 0; i < max + 1; ++i) { countArrary[i] = 0; } //3.遍历数组，获取统计数组值 for (int i = 0; i < len; ++i) { countArrary[arrary[i]]++; } //4.遍历统计数组，输出结果 int index = 0; int* sortedArrary = new int[len]; for (int i = 0; i < max + 1; ++i) { for (int j = 0; j < countArrary[i]; ++j) { sortedArrary[index++] = i; } } return sortedArrary; }

进阶： 解决两个问题：1.数组不是从0开始，如{95，91，92，91，98，96} 2.排序的相对稳定性（相同元素的前后顺序）

int* stableCountSort(int *arrary, int len) { //1.得到数列中最大，最小值 int max = INT_MIN; int min = INT_MAX; for (int i = 0; i < len; ++i) { if (arrary[i] > max) { max = arrary[i]; } if (arrary[i] < min) { min = arrary[i]; } } //2.计算差值，求出统计数组长度 int d = max - min; int* countArrary = new int[d + 1]; for (int i = 0; i < d + 1; ++i) { countArrary[i] = 0; } //3.遍历数组，获取统计数组值 for (int i = 0; i < len; ++i) { countArrary[arrary[i] - min]++; } //4.统计数组变形，后面元素等于前面元素之和 int sum = 0; for (int i = 0; i < d + 1; ++i) { sum += countArrary[i]; countArrary[i] = sum; } //5.倒序遍历原始数组，从统计数组找到正确位置，输出到结果数组 int* sortedArrary = new int[len]; for (int i = len - 1; i >= 0; --i) { sortedArrary[countArrary[arrary[i] - min] - 1] = arrary[i]; countArrary[arrary[i] - min]--; } return sortedArrary; }

四、局限性

1.当数列最大最小值差距过大时，并不适用于计数排序

比如给定20个随机整数，范围在0到1亿之间，此时如果使用计数排序的话，就需要创建长度为1亿的数组，不但严重浪费了空间，而且时间复杂度也随之升高。

2.当数列元素不是整数时，并不适用于计数排序

如果数列中的元素都是小数，比如3.1415，或是0.00000001这样子，则无法创建对应的统计数组，这样显然无法进行计数排序。

正是由于这两大局限性，才使得计数排序不像快速排序、归并排序那样被人们广泛适用。