计数排序

冒泡、选择、插入、归并、快速、希尔、堆排序，都是基于比较的排序，平均时间复杂度最低是O(nlogn)。

计数排序、桶排序、基数排序，都不是基于比较的排序，它们是典型的用空间换时间，在某些时候，平均时间复杂度可以比O(nlogn)更低。

计数排序（Counting Sort）于1954年由Harold H. Seward提出，适合对一定范围内的整数进行排序。

计数排序的核心思想：统计每个整数在数组中出现的次数，进而推导出每个整数在有序数组中的索引。

最简单的实现

具体实现步骤如下：

1. 找出数组array中的最大值max。
2. 开辟一个数组countsArray，数组大小为max+1,用于存放数组array中每个元素出现的次数，数组countsArray的索引为数组array的元素，数组countsArray值为数组array的元素出现的次数。
3. 遍历数组countsArray就可以得到有序数组。

代码实现如下：

// 找出最大值 int max = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > max) {         max = array[i]; } } // 开辟一个数组，用于存放每个元素出现的次数 int[] countsArray = new int[max + 1]; // 统计每个元素出现的次数 for (int i = 0; i < array.length; i++) {     countsArray[array[i]]++; } // 排序 int cur = 0; for (int i = 0; i < countsArray.length; i++) { while (countsArray[i]-- > 0) {         array[cur++] = i; } } 

这个实现存在以下问题：

• 无法对负整数进行排序，上面的实现中数组countsArray的索引为元素，而索引不可能出现负整数。
• 极其浪费内存空间，最小的元素以下的空间都是浪费。
• 是一个不稳定的排序。

计数排序优化

假设array中的最小值为min，最大值为max：

1. 开辟的计数数组countsArray大小为max-min+1，减少了空间的浪费。
2. array中的元素k对应的countsArray索引是k–min，值为元素出现的次数，与简单实现一样。
3. 数组countsArray中每个索引的值叠加前一个索引的值，这样所有值就对应有序数组中的索引。
4. 遍历数组array，array中的元素k在有序数组newArray（要新开辟一个数组来存放有序元素）中的索引为countsArray[k–min]–p，p代表着是倒数第几个k。

比如元素8在有序数组中的索引为countsArray[8–3]–1，结果为7。

倒数第1个元素7在有序序列中的索引countsArray[7-3]–1，结果为6。

倒数第2个元素7在有序序列中的索引countsArray[7–3]–2，结果为5。

代码实现如下：

// 找出最大值 int max = array[0]; // 找出最小值 int min = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > max) {         max = array[i]; } if (array[i] < min) {         min = array[i]; } } // 开辟一个数组，用于存放每个元素出现的次数 int[] countsArray = new int[max - min + 1]; // 统计每个元素出现的次数 for (int i = 0; i < array.length; i++) {     countsArray[array[i]]++; } // 每个次数叠加前面的次数 for (int i = 1; i < countsArray.length; i++) {     countsArray[i] += countsArray[i - 1]; } // 开辟一个新数据用来存放有序数组 int[] newArray = new int[array.length]; for (int i = array.length; i >= 0; i++) {     newArray[--countsArray[array[i] - min]] = array[i]; } // 将新数组数据覆盖旧数组 for (int i = 0; i < newArray.length; i++) {     array[i] = newArray[i]; } 

计数排序的最好、最坏、平均时间复杂度为O(n+k)，空间复杂度为O(n+k)（其中k是整数的取值范围），属于稳定排序。

更多精彩内容关注本人公众号：架构师升级之路