java使用索引排序是否有效

Question

所以我想了一个新的排序算法，可能会很有效，但我不太确定

1) Imagine we have an array a of only positive numbers.
2) We go through the array and find the biggest number n.
3) We create a new array b of the size n+1.
4) We go through every entry in the unsorted array and increase the value in the second array at the index of the number of the unsorted array we are looking at by one. (In pseudo-code this means: b[a[i]]++; while a[i] is the number we are currently looking at)
5) Once we have done this with every element in a, the array b stores at every index the exact amount of numbers of this index. (For example: b[0] = 3 means that we had 3 zeros in the initial array a)
6) We go through the whole array b and skip all the empty fields and create a new List or Array out of it.

所以我可以想象，这个算法可以非常快速有效地处理较小的数字，因为最后我们必须遍历整个数组b来构建排序后的数组，这将非常耗时
例如，如果我们有一个数组a={1000，1}，它仍然会检查数组b中的1001个元素是否为0，即使初始数组中只有2个元素。
然而，对于较小的数字，我们应该几乎得到一个O（n）结果？我对此不太确定，这就是为什么我要问你。也许我甚至错过了一些真正重要的东西
提前感谢您的帮助：）

Answer 1

祝贺你独立地重新发现了counting sort

这确实是一个非常好的排序策略，适用于范围有限的情况，并且项目数明显大于数组中的项目数

在范围大于数组中项目数的情况下，传统的排序算法将提供更好的性能

这种算法被称为pseudo-polynomial

Answer 2

we should almost get a O(n) result

当第一个数组中的最大数为M时，得到O（N+M）的结果。另外，你需要消耗O（M）内存，所以只有当M很小时才有意义。见counting sort