sorting - 计数排序可以对十进制值进行排序吗？

Question

计数排序可以对十进制值进行排序吗？我最近才开始学习java，我不确定。有谁知道它是否可以？

标签： sorting

Answer 1

计数排序之所以有效，是因为您确切地知道数组中有多少个元素，并且因为数组中的每个索引都代表一个具有相同值的整数。数组[1, 2, 0, 2, 1]可以表示为[1, 2, 2]排序的中间阶段。有一个 0、两个 1 和两个 2。

这对于小数来说是不可能的。如果您可以确保一定程度的精度，我想您可以为每个潜在值添加一个插槽。例如，如果所有小数都四舍五入到最接近的十分之一，则每个整数需要 10 个插槽加上 0 的 1 个插槽：0.1、0.2、0.3、0.4、0.5、0.6、0.7、0.8、0.9、1.0

// the original array
[0.1, 1.1, 0.7, 1.4, 0.5, 0.7]


// after the counting step

// 0.0  0.1  0.2  0.3  0.4  0.5  0.6  0.7  0.8  0.9
[   0    1    0    0    0    1    0    2    0    0

// 1.1  1.2  1.2  1.3  1.4  1.5  1.6  1.7  1.8  1.9
    1    0    0    0    1    0    0    0    0    0 ]

// when expanded to the sorted array

[0.1, 0.5, 0.7, 0.7, 1.1, 1.4]

因此，对于最大值为 N 的排序，计数数组 (K) 的大小将为 N * 10。因此 k = 10N。这显然不是真正的计数排序，因为计数步骤会更复杂，因为每个值都不能很容易地映射到索引。

因此，虽然理论上可能并且具有相同的时间复杂度，但它不会是“真正的”计数排序，同时也会占用更多的内存空间以实现实用，特别是在以高精度对大数字范围进行排序时，并且比其他方法更不灵活排序算法。最好使用大多数其他排序算法。