一尘不染

使用预定义的排序值列表对对象进行排序

algorithm

我想知道最快的方法是按与其他数组相同的顺序对对象数组进行排序。

这是C#中的示例:

class MyClass
{
    public MyClass(int value)
    {
        this.value = value;
    }
    int value;
    public int Value
    {
        get { return value; }
        set { this.value = value; }
    }
}


    static List<int> sortedValuesList;
    static List<MyClass> objectList;

用与sortedValuesList相同的顺序对objectList进行排序的最快方法是什么?可能有多个具有相同值的对象。

我已经有一个简单的算法可以做到,但是它是O(n ^ 2),需要额外的内存。

编辑:
我想不清楚我想做什么。假设用户在屏幕上看到销售人员的数据网格。他可以按所需的任何列对它们进行排序。现在,用户单击一个按钮,将显示一个客户表。每个客户都引用一位销售人员。我想根据先前数据网格中销售人员的顺序对客户列表进行排序。

这只是一个理论问题,因为我不需要更多性能。我只是想知道当您需要使用查找表比较对象时是否有一些不错的排序算法。


阅读 207

收藏
2020-07-28

共1个答案

一尘不染

将其分为以下步骤:

  1. 浏览您的sortedValuesList并从值->索引位置构建一个映射;这是O(n log n)
  2. 遍历对象并将索引添加到一个临时字段中(同样,O(n log n))
  3. 按临时字段对列表进行排序(也为O(n log n))

总算法,O(n log n)。

另外,如果您不希望有暂存字段,则可以每次通过地图查找排序关键字,以获得整体O(n(log n)^ 2)

2020-07-28