java - 这种 O(n) 排序方法已经存在了吗？

Question

这个想法是将所有值设置为其最终数组中的父索引，然后删除所有空值。 这是一些简单的实现:

int x[] = {9,3,4,2,1,12,5};
sortList(x)

public static int[] sortList(int[] x){
    int[] y = new int[15];
    for (int i=0; i < x.length; i++){
        int value = x[i];
        y[value] = value;
    }
    return removeNull(y);
}
public static int[] removeNull(int[] array) {
    return Arrays.stream(array).filter(i -> i != 0).toArray();
}

请注意，它仅对唯一的非零值进行排序。这是该方法在遍历数组时所做的事情:

数组 -> 9,3,4,2,1,5 将转换为 -> 0,1,2,3,4,5,0,0,0,9,0,0 然后转换为-> 1,2,3,4,5,9 如果我正确的话，这个解决方案将循环数组 3 次并采用 y 大小作为存储。这种排序方法已经存在吗？

Answer 1

该算法被称为 Counting Sort 。

这是维基百科的描述:

In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items.

正如您所指出的，您的算法会丢弃重复项。计数排序因其解决该问题而得名:计算每个键的项数。该算法确实是线性的，但时间和空间常数因子都很高，因此在实际中很少使用。