C# Реализация Radix Sort в LinkedList - PullRequest
Новая
       83

C# Реализация Radix Sort в LinkedList

0 голосов
/ 27 апреля 2020

У меня есть задача создать алгоритм сортировки по основанию для класса связанного списка, у меня есть объект "Информация", который имеет int Год и двойную цену, мне нужно отсортировать связанный список по году, используя сортировку по основанию. 

    class Info
    {
        public int Year { get; set; }
        public double Price { get; set; }
        public Info() { }
        public Info(int y, double p)
        {
            Year = y;
            Price = p;
        }
    }

    class Node
    {
        public Info Data { get; set; }
        public Node Next { get; set; }
        public Node(Info data, Node adress)
        {
            Data = data;
            Next = adress;
        }
    }

    class LinkedList
    {
        private Node First;
        private Node Last;
        private Node Current;
        public LinkedList()
        {
            First = null;
            Last = null;
            Current = null;
        }
     }

И я взял алгоритм радикальной сортировки целых чисел с этого сайта . Проблема в том, что я не знаю, как изменить его для работы с моим связанным классом. 

        static void Sort(int[] arr)
        {
            int temp = 0;
            int i, j;
            int[] tmp = new int[arr.Length];
            for (int shift = 31; shift > -1; --shift)
            {
                j = 0;
                for (i = 0; i < arr.Length; ++i)
                {
                    bool move = (arr[i] << shift) >= 0;
                    if (shift == 0 ? !move : move)
                        arr[i - j] = arr[i];
                    else
                        tmp[j++] = arr[i];
                }
                Array.Copy(tmp, 0, arr, arr.Length - j, j);
            }
        }

Как заставить его работать с моим связанным классом?

1 Ответ

0 голосов
/ 28 апреля 2020

На основании этого кода arr и tmp должны быть связаны списками. Одна из проблем этого подхода заключается в том, что перемещение узла требует отслеживания предыдущих узлов для перемещения узла. Пустой головной узел может использоваться для предоставления узла, предшествующего первому узлу данных, или для передачи в особом случае при перемещении узла в начало списка. Альтернативой может быть использование двух указателей (ссылок) на узлы временных списков, один где бит == 0, другой где бит == 1, а затем объединение двух временных списков в один список. Обратите внимание, что этот подход занимает 32 прохода. Если бы радикальная сортировка основывалась на байте, а не на бите, ее можно было бы уменьшить до 4 проходов, но для узлов из 256 списков потребовалось бы 256 указателей.

...