所以我有一张物品清单。都是同一类型的。我们叫它福吧。Foo有一个属性" value“,我想按该值进行排序。我已经用Java实现了这个算法。它是通用的,我提供了两个例子。一种使用整数,另一种使用枚举常量作为值的类型。
该算法简单地对所有可能的值进行迭代,然后迭代每个这样的值的输入列表。所有具有相同值的元素都会添加到结果列表中。就是这样。
如果有11个值,那么它将迭代列表11次。因此,时间复杂度为O(11*n)。但是11是一个常数,所以它实际上是O(n),这对于排序算法是很好的。即使有数以十亿计的数值,它仍然是O(n)。假设是正确的吗?
实际上,我在一些我必须处理的代码中发现了类似的东西。我花了一段时间才弄明白这段代码是真的,因为我不希望任何人在没有充分理由的情况下实际实现排序算法。代码是由不知道Java允许您按Collections.sort(myList, Comparator.comparing(Foo::getValue))排序的人编写的。
起初我认为这是一个糟糕的列表排序方法,但后来我意识到它实际上是非常快甚至稳定的。但它还没有到位。我想知道那个算法的名字是什么。
在实际数据上进行测试时,常见算法(如快速排序)的性能可能仍然要好得多。所以我想知道这个是否曾经被使用过。
下面是代码:
import java.util.*;
import java.util.function.Function;
import java.util.stream.*;
public class SortAlgo {
/**
* Sorts a list. The sort is stable.
* The input won't be changed. A new list is returned instead.
*
* @param list
* The list to be sorted.
* @param values
* The possible values of the field used for the sorting.
* @param get
* A function to get the value.
* @return A new, sorted list.
*/
public static <T, V> List<T> sort(final List<T> list, final List<V> values,
final Function<T, V> get) {
final List<T> result = new ArrayList<>(list.size());
for (final V v : values)
for (final T t : list)
if (get.apply(t) == v)
result.add(t);
assert result.size() == list.size();
return result;
}
static class Foo1 {
public static final int MIN_VALUE = 0;
public static final int MAX_VALUE = 10;
final private int value;
public Foo1(final int value) {
this.value = value;
}
public int getValue() {
return this.value;
}
@Override
public String toString() {
return Integer.toString(this.value);
}
}
static class Foo2 {
public static enum Value {
A, B, C, D, E;
}
final private Value value;
public Foo2(final Value value) {
this.value = value;
}
public Value getValue() {
return this.value;
}
@Override
public String toString() {
return this.value.name();
}
}
public static void main(final String[] args) {
final List<Foo1> list1 = new ArrayList<>();
final Random rng = new Random();
for (int i = 0; i < 100; i++)
list1.add(new Foo1(rng.nextInt(Foo1.MAX_VALUE + 1)));
final List<Integer> values1 = IntStream.rangeClosed(Foo1.MIN_VALUE, Foo1.MAX_VALUE).boxed()
.collect(Collectors.toList());
final List<Foo1> sorted1 = sort(list1, values1, Foo1::getValue);
System.out.println(sorted1);
// -------------------------
final List<Foo2> list2 = new ArrayList<>();
final Foo2.Value[] enums = Foo2.Value.values();
for (int i = 0; i < 100; i++)
list2.add(new Foo2(enums[rng.nextInt(enums.length)]));
final List<Foo2.Value> values2 = Arrays.asList(enums);
final List<Foo2> sorted2 = sort(list2, values2, Foo2::getValue);
System.out.println(sorted2);
}
}发布于 2015-10-24 22:19:59
它本质上是一个计数排序,它是O(n),但是有一个额外的循环,而不是将值存储在数组中,只循环一次。
https://stackoverflow.com/questions/33323805
复制相似问题