jdk中如何实现计数排序

这篇文章将为大家详细讲解有关jdk中如何实现计数排序，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。

        计数排序是一个非基于比较的排序算法，它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。我们估计要有疑问了，这个排序算法这么快，为什么还存在其他的排序算法呢，这就需要要我们综合时间复杂度和空间复杂度那个最优了。

        Java底层对不同的数据实现了各种各样的排序算法，而对于计数排序只有在比较byte类型的数字才有效，也就是说数字最大也就是256.Java底层对这个算法实现的相当精巧，基本实现过程如下：（详情可以打开jdk java.util.Arrays.sort(byte[])）。

1：初始化一个计数数组，大小是输入数组中的最大的数。

2：遍历输入数组，遇到一个数就在计数数组对应的位置上加一。例如：遇到7，就将计数数组第七个位置的数加一。

3：把计数数组直接覆盖到输出数组（节约空间）。

源码如下：

在jdk中这段代码还是存在优化的空间，我完全可以把初始化数组变得更小，更节省内存，即用多少初始化多少， 举个例子：

比如说我输入了一个数组{4, 1, 4, 2, 3}，初始化数组大小为4即可，（按照算法导论中对计数排序的理论，即：计数数组的大小为排序数组中数字最大的数）

建立计数数组{0, 0, 0, 0}。

遍历输入数组：

{3, 4, 3, 2, 1} -> {0, 0, 1, 0}

{3, 4, 3, 2, 1} -> {0, 0, 1, 1}

{3, 4, 3, 2, 1} -> {0, 0, 2, 1}

{3, 4, 3, 2, 1} -> {0, 1, 2, 1}

{3, 4, 3, 2, 1} -> {1, 1, 2, 1}

计数数组现在是{1, 1, 2, 1}，我们现在把它写回到输入数组里：

{0, 1, 2, 1} -> {1, 4, 3, 2, 1}

{0, 0, 2, 1} -> {1, 2, 3, 2, 1}

{0, 0, 1, 1} -> {1, 2, 3, 2, 1}

{0, 0, 0, 1} -> {1, 2, 3, 3, 1}

{0, 0, 0, 0} -> {1, 2, 3, 3, 4}

这样就排好序了。

时间：O(n + k)，n是输入数组长度，k是最大的数的大小。

空间：O(n + k)，n是输入数组长度，k是最大的数的大小。

关于“jdk中如何实现计数排序”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。