首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >这种分类方法的名称和时间复杂度是多少?

这种分类方法的名称和时间复杂度是多少?
EN

Stack Overflow用户
提问于 2015-10-24 21:57:21
回答 1查看 56关注 0票数 0

所以我有一张物品清单。都是同一类型的。我们叫它福吧。Foo有一个属性" value“,我想按该值进行排序。我已经用Java实现了这个算法。它是通用的,我提供了两个例子。一种使用整数,另一种使用枚举常量作为值的类型。

该算法简单地对所有可能的值进行迭代,然后迭代每个这样的值的输入列表。所有具有相同值的元素都会添加到结果列表中。就是这样。

如果有11个值,那么它将迭代列表11次。因此,时间复杂度为O(11*n)。但是11是一个常数,所以它实际上是O(n),这对于排序算法是很好的。即使有数以十亿计的数值,它仍然是O(n)。假设是正确的吗?

实际上,我在一些我必须处理的代码中发现了类似的东西。我花了一段时间才弄明白这段代码是真的,因为我不希望任何人在没有充分理由的情况下实际实现排序算法。代码是由不知道Java允许您按Collections.sort(myList, Comparator.comparing(Foo::getValue))排序的人编写的。

起初我认为这是一个糟糕的列表排序方法,但后来我意识到它实际上是非常快甚至稳定的。但它还没有到位。我想知道那个算法的名字是什么。

在实际数据上进行测试时,常见算法(如快速排序)的性能可能仍然要好得多。所以我想知道这个是否曾经被使用过。

下面是代码:

代码语言:javascript
复制
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);

  }

}
EN

回答 1

Stack Overflow用户

发布于 2015-10-24 22:19:59

它本质上是一个计数排序,它是O(n),但是有一个额外的循环,而不是将值存储在数组中,只循环一次。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/33323805

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档