Сортировка двусвязного списка

@boriskudinow · Регистрация: 13.04.2021

Студворк — интернет-сервис помощи студентам

Имеется вот такой вот двусвязный список, как сделать его быструю сортировку?

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Program
    {
        static void Main(string[] args)
        {           
            DoublyLinkedList<int> list = new DoublyLinkedList<int>();
            list.Add2Begin(1); // добавление в начало
            list.Add2Begin(2);
            list.Add2Begin(4);
            list.Add2End(5); // добавление в конец
            list.Add2End(9);
            list.PrintNodes();
            Console.WriteLine("Size = " + list.Size);
            Console.ReadKey();           
        }
        public class Node<T>
        {
            public T Value; // поле Value
            public Node<T> Previous; // ссылка на предыдущий элемент
            public Node<T> Next; // ссылка на следующий элемент
            public Node(T value, Node<T> previous = null, Node<T> next = null) // конструктор нового элемента
            { 
                Value = value; Previous = previous; Next = next; 
            }
        }
        class DoublyLinkedList<T>
        {
            public uint Size; // размер списка
            private Node<T> First; // первый элемент списка
            private Node<T> Last; // последний элемент списка
            public void Add2Begin(T value)
            {
                Node<T> node = new Node<T>(value, null, First);
                if (First == null) { First = node; Last = node; }
                else { First.Previous = node; First = node; }
                Size++;
            }
            public void Add2End(T value)
            {
                Node<T> node = new Node<T>(value, Last, null);
                if (Last == null) { First = node; Last = node; }
                else { Last.Next = node; Last = node; }
                Size++;
            }
            public void PrintNodes()
            {
                Console.Write("Список слева направо: ");
                Node<T> Temp = First;
                while (Temp != null)
                {
                    Console.Write(" " + Temp.Value);
                    Temp = Temp.Next;
                }
                Console.WriteLine();               
            }
        }
    }

PokerMagnat · 14.04.2021, 20:53

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
class Program
{
  static void Main(string[] args)
  {           
      DoublyLinkedList<int> list = new DoublyLinkedList<int>();
      list.Add2Begin(1); // добавление в начало
      list.Add2Begin(2);
      list.Add2Begin(4);
      list.Add2End(5); // добавление в конец
      list.Add2End(9);
      list.PrintNodes();
      Console.WriteLine("Size = " + list.Size);
      list.sort();
      Console.WriteLine("Sorted list: ");
      list.PrintNodes();
      Console.ReadKey();           
  }
 
  public class Node<T>
  {
      public T Value; // поле Value
      public Node<T> Previous; // ссылка на предыдущий элемент
      public Node<T> Next; // ссылка на следующий элемент
      public Node(T value, Node<T> previous = null, Node<T> next = null) // конструктор нового элемента
      { 
          Value = value; Previous = previous; Next = next; 
      }
  }
 
  class DoublyLinkedList<T> where T: IComparable<T>
  {
      public uint Size; // размер списка
      private Node<T> First; // первый элемент списка
      private Node<T> Last; // последний элемент списка
      public void Add2Begin(T value)
      {
          Node<T> node = new Node<T>(value, null, First);
          if (First == null) { First = node; Last = node; }
          else { First.Previous = node; First = node; }
          Size++;
      }
      public void Add2End(T value)
      {
          Node<T> node = new Node<T>(value, Last, null);
          if (Last == null) { First = node; Last = node; }
          else { Last.Next = node; Last = node; }
          Size++;
      }
      public void PrintNodes()
      {
          Console.Write("Список слева направо: ");
          Node<T> Temp = First;
          while (Temp != null)
          {
              Console.Write(" " + Temp.Value);
              Temp = Temp.Next;
          }
          Console.WriteLine();               
      }
 
      public void sort()
      {
        quickSort(First, Last);
      }
 
      private void quickSort(Node<T> lo, Node<T> hi)
      {
        if (lo != null && hi != null && lo != hi && lo != hi.Next)
        {
          Node<T> p = partition(lo, hi);
          quickSort(lo, p.Previous);
          quickSort(p.Next, hi);
        }
      }
 
      private Node<T> partition(Node<T> lo, Node<T> hi)
      {
        Node<T> pivot = hi;
        Node<T> i = lo, j = lo;
        while (j != hi)
        {
          if (j.Value.CompareTo(pivot.Value) < 0)
          {
            swap(j, i);
            i = i.Next;
          }
          j = j.Next;
        }
        swap(i, pivot);
        return i;
      }
 
      private void swap(Node<T> a, Node<T> b)
      {
        T temp = a.Value;
        a.Value = b.Value;
        b.Value = temp;
      }
  }
}

Новые блоги и статьи Все статьи Все блоги /
Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .