Сортировка объектов с использованием предварительно определенного списка отсортированных значений

Question

Мне было интересно, что будет самым быстрым способом сортировки массива объектов в том же порядке, что и другой массив.

Вот пример на 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;

Какой самый быстрый способ сортировки objectList в том же порядке, что и sortedValuesList? Может быть несколько объектов с одинаковым значением.

У меня уже есть простой алгоритм, который может это сделать, но он O (n ^ 2) и требует дополнительной памяти.

EDIT: Думаю, не ясно, что я пытаюсь сделать. Допустим, пользователь видит на экране сетку данных продавцов. Он может отсортировать их по любому столбцу, который он хочет. Теперь пользователь нажимает на кнопку, и отображается таблица клиентов. Каждый покупатель ссылается на одного из продавцов. Я хочу отсортировать список клиентов на основе порядка продавцов в предыдущей сетке данных.

Это только теоретический вопрос, так как мне не нужно больше производительности. Мне просто интересно, есть ли какой-нибудь хороший алгоритм сортировки, когда вам нужно использовать справочную таблицу для сравнения объектов.

Answer 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)

Answer 2

Во-первых, сделайте себе одолжение и используйте универсальную версию List, поэтому определите ваш objectList как

static List<MyClass> objectList;

Но в любом случае, поскольку список представляет собой набор ссылок на реальные объекты, и, поскольку вы, кажется, хотите, чтобы два списка были в одном и том же порядке, почему бы просто не назначить один список другому? Что мне не хватает?

Answer 3

Звучит так, будто вы хотите карту вместо:

static Dictionary<int, MyClass> sortedObjectList

Answer 4

Вот мое очень простое решение: </p> <pre><code>class Program { static List<int> sortedValuesList; static List<MyClass> objectList; static void Main(string[] args) { //Generate some test data; Random random = new Random(); objectList = new List<MyClass>(); sortedValuesList = new List<int>(); for (int i = 0; i < 10; i++) { MyClass a = new MyClass(random.Next() % 20); objectList.Add(a); if (!sortedValuesList.Contains(a.Value)) sortedValuesList.Add(a.Value); } //Shuffle id's for (int i = sortedValuesList.Count - 1; i > 0; i--) { int n = random.Next(i + 1); int tempId = sortedValuesList[n]; sortedValuesList[n] = sortedValuesList[i]; sortedValuesList[i] = tempId; } Console.WriteLine("Reference list:"); for (int i = 0; i < sortedValuesList.Count; i++) { Console.WriteLine(string.Format("{0,2} {1,5}", i, sortedValuesList[i])); } Console.WriteLine("unsorted list:"); for (int i = 0; i < objectList.Count; i++) { Console.WriteLine(string.Format("{0,2} {1,5}", i, objectList[i].Value)); } //Sort List<MyClass> sortedList = new List<MyClass>(); foreach (int id in sortedValuesList) { sortedList.AddRange( objectList.FindAll(delegate(MyClass a) { return a.Value == id; }) ); } Console.WriteLine("After sorting:"); for (int i = 0; i < sortedList.Count; i++) { Console.WriteLine(string.Format("{0,2} {1,5}", i, sortedList[i].Value)); } Console.ReadKey(); } }