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


【AD】美国洛杉矶/香港/日本VPS推荐,回程电信CN2 GIA线路,延迟低、稳定性高、免费备份_搬瓦工

【AD】炭云:36元/年/1GB内存/20GB SSD空间/500GB流量/5Gbps端口/KVM/香港/国际线路LUMEN