使用 C# 对自定义链接列表进行排序

Question

我创建了一个自定义链表，代码如下。现在尝试实现一种排序（这是我告诉要做的，不是我知道的最佳选择），我们如何以最佳时间复杂度或最佳方法进行

我的自定义链表我的疑问是最后一个节点，在冒泡排序的每个阶段都应该尝试最后排序然后从第一个节点开始，如何处理最后一个节点指向第一个节点

    public class CustomCircularList<T> : ICollection<T>, IEnumerable<T>
    {

        Node<T> head = null;
        Node<T> tail = null;
        int count = 0;
        readonly IEqualityComparer<T> comparer;

        public int Count { get { return count; } }
        public bool IsReadOnly { get { return false; } }

        public void Add(T item)
        {
            this.AddLast(item);
        }
         AddLast...
    }
}

我的节点class具有三个属性

public T Value { get; private set; }
public Node<T> Next { get; set; }
public Node<T> Previous { get; set; }

我像这样将 IComparer 添加到我的 class T 并尝试像下面那样工作

 public class Fund: IComparer<Fund>
    {
        public string fundname{ get; set; }
        public int Compare([AllowNull] Fund x, [AllowNull] Fund y)
        {
            if (x == null || y == null)
            {
                return 0;
            }

            return x.fundname.CompareTo(y.fundname);
      }

Answer 1

首先，让我假设 Node<T> 对象具有（至少）2 个标准属性：Value 和 Next:

public class Node<T> {
  ...
  public T Value {get; set;}
  public Node<T> Next {get;} 
}

因为你有循环链表，

tail.Next == head

我们可以枚举所有项除了最后一项为

for (Node<T> node = head; !ReferenceEquals(node.Next, head); node = node.Next) {
  ...
}

仅供参考，如果我们有一个链表（非循环），循环将是（我们只需要将head更改为null):

for (Node<T> node = head; !ReferenceEquals(node.Next, null); node = node.Next) {
  ...
}

代码可以

public void BubbleSort(IComparer<T> comparer = null) {
  comparer ??= Comparer<T>.Default;

  if (comparer is null)
    throw new ArgumentNullException(nameof(comparer));

  if (head is null)
    return; // empty linked list

  bool agenda = true;

  while (agenda) {
    agenda = false;

    for (Node<T> node = head; !ReferenceEquals(node.Next, head); node = node.Next) 
      if (comparer.Compare(node.Value, node.Next.Value) > 0) {
        agenda = true;

        var help = node.Value; 
        node.Value = node.Next.Value;
        node.Next.Value = help;   
      } 
  } 
}

编辑： 如果你想对某些自定义类型 (T) 进行排序，你应该确保 T 实现 IComparable<T>:

public class MyClass: IComparable<MyClass> {
  ...
  public int CompareTo(MyClass other) {
    TODO: return 0 if other == this, -1 if this < other, +1 if this > other
  }
}

或者您应该实现一个 comparer IComparer<MyClass>，您应该将其作为参数提供：

public class MyComparer<MyClass> {
  public int Compare(MyClass x, MyClass y) {
    //TODO: return 0 when x == y, -1 when x < y, when x > y
  }
}

然后

MyCircularLinkedList.BubbleSort(new MyComparer());

使用 C# 对自定义链接列表进行排序

Sort on a custom Linked List using c#

c#

sorting

algorithm

data-structures