logo标签列表

链表排序

c#algorithmdata-structureslinked-list
13
我用C#编写了一个基本的链表类，其中有一个节点对象，代表着链表中的每个节点。
虽然代码没有使用IEnumerable，但我能否实现排序函数？ 我使用的编程语言是C#。是否有关于此的C#示例？
我正在参考这个示例：
谢谢！
9个回答
23

功能性快排和归并排序

以下是使用函数式风格编写的快速排序和归并排序方法：

class List
{
    public int item;
    public List rest;

    public List(int item, List rest)
    {
        this.item = item;
        this.rest = rest;
    }

    // helper methods for quicksort

    public static List Append(List xs, List ys)
    {
        if (xs == null) return ys;
        else return new List(xs.item, Append(xs.rest, ys));
    }

    public static List Filter(Func<int,bool> p, List xs)
    {
        if (xs == null) return null;
        else if (p(xs.item)) return new List(xs.item, Filter(p, xs.rest));
        else return Filter(p, xs.rest);
    }

    public static List QSort(List xs)
    {
        if (xs == null) return null;
        else
        {
            int pivot = xs.item;
            List less = QSort(Filter(x => x <= pivot, xs.rest));
            List more = QSort(Filter(x => x > pivot, xs.rest));
            return Append(less, new List(pivot, more));
        }
    }

    // Helper methods for mergesort

    public static int Length(List xs)
    {
        if (xs == null) return 0;
        else return 1 + Length(xs.rest);
    }

    public static List Take(int n, List xs)
    {
        if (n == 0) return null;
        else return new List(xs.item, Take(n - 1, xs.rest));
    }

    public static List Drop(int n, List xs)
    {
        if (n == 0) return xs;
        else return Drop(n - 1, xs.rest);
    }

    public static List Merge(List xs, List ys)
    {
        if (xs == null) return ys;
        else if (ys == null) return xs;
        else if (xs.item <= ys.item) return new List(xs.item, Merge(xs.rest, ys));
        else return new List(ys.item, Merge(xs, ys.rest));
    }

    public static List MSort(List xs)
    {
        if (Length(xs) <= 1) return xs;
        else
        {
            int len = Length(xs) / 2;
            List left  = MSort(Take(len, xs));
            List right = MSort(Drop(len, xs));
            return Merge(left, right);
        }
    }

    public static string Show(List xs)
    {
        if(xs == null) return "";
        else return xs.item.ToString() + " " + Show(xs.rest);
    }
}

使用Pairing堆实现函数式堆排序

额外加分项：使用函数式Pairing堆进行堆排序。

class List
{
    // ...

    public static Heap List2Heap(List xs)
    {
        if (xs == null) return null;
        else return Heap.Merge(new Heap(null, xs.item, null), List2Heap(xs.rest));
    }

    public static List HSort(List xs)
    {
        return Heap.Heap2List(List2Heap(xs));
    }
}

class Heap
{
    Heap left;
    int min;
    Heap right;

    public Heap(Heap left, int min, Heap right)
    {
        this.left = left;
        this.min = min;
        this.right = right;
    }

    public static Heap Merge(Heap a, Heap b)
    {
        if (a == null) return b;
        if (b == null) return a;

        Heap smaller = a.min <= b.min ? a : b;
        Heap larger = a.min <= b.min ? b : a;
        return new Heap(smaller.left, smaller.min, Merge(smaller.right, larger));
    }

    public static Heap DeleteMin(Heap a)
    {
        return Merge(a.left, a.right);
    }

    public static List Heap2List(Heap a)
    {
        if (a == null) return null;
        else return new List(a.min, Heap2List(DeleteMin(a)));
    }
}

为了实际使用，您需要重写辅助方法而不使用递归，并且可能使用内置的可变列表。

使用方法：

List xs = new List(4, new List(2, new List(3, new List(1, null))));
Console.WriteLine(List.Show(List.QSort(xs)));
Console.WriteLine(List.Show(List.MSort(xs)));
Console.WriteLine(List.Show(List.HSort(xs)));

链表的原地快速排序

请求提供一个原地版本。这里是一个非常快速的实现。我一字不漏地编写了这个代码，没有寻找改进代码的机会，也就是说每一行都是我首先想到的。因为我使用 null 作为空列表，所以它非常丑陋 :) 缩进不一致等等。

此外，我仅在一个示例上测试了这个代码:

        MList ys = new MList(4, new MList(2, new MList(3, new MList(1, null))));
        MList.QSortInPlace(ref ys);
        Console.WriteLine(MList.Show(ys));

神奇的是它第一次就可行了！但我相当确定这段代码包含了一些bug，请不要追究我。

class MList
{
    public int item;
    public MList rest;

    public MList(int item, MList rest)
    {
        this.item = item;
        this.rest = rest;
    }

    public static void QSortInPlace(ref MList xs)
    {
        if (xs == null) return;

        int pivot = xs.item;
        MList pivotNode = xs;
        xs = xs.rest;
        pivotNode.rest = null;
        // partition the list into two parts
        MList smaller = null; // items smaller than pivot
        MList larger = null; // items larger than pivot
        while (xs != null)
        {
            var rest = xs.rest;
            if (xs.item < pivot) {
                xs.rest = smaller;
                smaller = xs;
            } else {
                xs.rest = larger;
                larger = xs;
            }
            xs = rest;
        }

        // sort the smaller and larger lists
        QSortInPlace(ref smaller);
        QSortInPlace(ref larger);

        // append smaller + [pivot] + larger
        AppendInPlace(ref pivotNode, larger);
        AppendInPlace(ref smaller, pivotNode);
        xs = smaller;
    }

    public static void AppendInPlace(ref MList xs, MList ys)
    {
        if(xs == null){
            xs = ys;
            return;
        }

        // find the last node in xs
        MList last = xs;
        while (last.rest != null)
        {
            last = last.rest;
        }
        last.rest = ys;
    }

    public static string Show(MList xs)
    {
        if (xs == null) return "";
        else return xs.item.ToString() + " " + Show(xs.rest);
    }
}
我不确定它是如何工作的。我知道快速排序在理论上是如何工作的，但我不确定这段代码。 你能给我展示一个使用快速排序对列表进行排序并在完成后显示已排序列表的例子吗？ - CasperT
1
我添加了一个例子。这个快速排序的工作方式如下：选择第一项作为枢轴。然后将剩余的项目分成两个列表：小于或等于枢轴的所有项目都包含在“less”列表中，而其余的项目（大于枢轴的项目）则包含在“more”列表中。下一步是分别对这两个列表进行排序。完成后，我们按照顺序从三个部分构建一个列表，即less + pivot + more。 - Jules
我已经仔细查找，但无法在你的qsort函数中找到“x”的定义。 你能否编辑一下？我觉得这很有趣。 - baash05
@Aseraphim：我想看看你如何在链表上实现原地排序。使用O(n^2)排序很容易，但对于快速排序和归并排序，我不会那么快地说它是可能的。 - ephemient
过滤器（Filter）在哪里？ - nim
显示剩余5条评论
10

当然可以使用普通的链表实现排序函数。 归并排序 可能是一个适合尝试的算法，它相当简单。

+1 建议使用归并排序，这非常适合链表。 - Brian
7
最简单的方法可能是提取数据，将其排序在已经支持排序的机制中（数组、List<T> 或者通过LINQ的 IEnumerable<T>），并重新用排序后的数据重建链表。
如果你想编写自己的排序算法，那么你可能会发现 Comparer<T>.Default 很有用（假设你使用泛型）。这应该允许你比较任何实现了 IComparable<T> 或者 IComparable 接口的项目。
顺便说一下 - 请注意，.NET 已经包括了 LinkedList<T> 等；如果这只是为了学习等目的，那就没问题了 ;-p
1
抱歉伙计，我不得不给你投反对票。我想谁实现了他们自己的链表都有他们的原因（虽然我无法想出一个，但也许有）。我曾在面试中遇到过这样的问题，我怀疑说使用STL可能不够。 - baash05
1
好吧...有点诡异- 4周前的回复，在2天内被踩了3次？可能有些可疑的事情发生了... - Marc Gravell
2
我坚持我的回复baash05：关于你的评论“我怀疑说使用STL就足够了” - 在面试时，如果没有充分的理由不选择预先制作的BCL，我会质疑任何人的理智。OP没有说明原因，因此BCL应该是默认选择。 - Marc Gravell
我试着帮你撤销 Marc 的反对票...假设 Marc，你来到一个本地实现了链表的项目，你必须对其进行排序。将其转移到STL中，然后再转回来，以便应用程序的其余部分可以使用它，这将对资源造成巨大的压力，更不用说内存了。问题没有说不要使用，但也没有说不要将其发送到印度让别人来做。它只是问了如何操作，而你没有回答如何操作。尽管如此，我不认同给出巨大反对意见。我讨厌答案上的负值。它们会抵消努力，而我告诉你，我感激“我们”所有的努力。 - baash05
5

有些人（包括我）可能想对来自.net库的LinkedList<T>进行排序。

简单的方法是使用Linq排序，最后创建一个新的链表。但这会产生垃圾。对于小集合来说，这不是问题，但对于大集合来说，效率可能不高。

对于想要一定程度优化的人，这里提供了一个通用的在.net双向链表中实现的原地快速排序。

此实现不进行分裂/合并，而是检查每个递归的边界节点。

/// <summary>
/// in place linked list sort using quick sort.
/// </summary>
public static void QuickSort<T>(this LinkedList<T> linkedList, IComparer<T> comparer)
{
    if (linkedList == null || linkedList.Count <= 1) return; // there is nothing to sort
    SortImpl(linkedList.First, linkedList.Last, comparer);
}

private static void SortImpl<T>(LinkedListNode<T> head, LinkedListNode<T> tail, IComparer<T> comparer)
{
    if (head == tail) return; // there is nothing to sort

    void Swap(LinkedListNode<T> a, LinkedListNode<T> b)
    {
        var tmp = a.Value;
        a.Value = b.Value;
        b.Value = tmp;
    }

    var pivot = tail;
    var node = head;
    while (node.Next != pivot)
    {
        if (comparer.Compare(node.Value, pivot.Value) > 0)
        {
            Swap(pivot, pivot.Previous);
            Swap(node, pivot);
            pivot = pivot.Previous; // move pivot backward
        }
        else node = node.Next; // move node forward
    }
    if (comparer.Compare(node.Value, pivot.Value) > 0)
    {
        Swap(node, pivot);
        pivot = node;
    }

    // pivot location is found, now sort nodes below and above pivot.
    // if head or tail is equal to pivot we reached boundaries and we should stop recursion.
    if (head != pivot) SortImpl(head, pivot.Previous, comparer);
    if (tail != pivot) SortImpl(pivot.Next, tail, comparer);
}
它的时间复杂度是否与快速排序相同，最佳为nlog(n)，平均为nlog(n)，最差为n^2，空间复杂度为log(n)？ - Alexander Danilov
1
对于大型列表，它会抛出堆栈溢出异常。 - Alexander Danilov
由于它总是将最后一个元素作为枢轴，如果列表已经排序，则其性能将表现不佳（但由于它是链表且没有简单的方法选择更好的枢轴，因此您无法做太多事情）。 - tigrou
1
for(int i=0; i<counter;i++)
{
  while(current.next!=null)
  {
    if(current.elemen>current.next.element)
    {
      Swap(current.elment,current.next.element);
    }
    current=current.next;
  }
}

当您向链表添加或插入元素时，增加计数器

1

这可能不是最佳解决方案，但它是我能想到的最简单的。如果有人能想到更简单但仍然快速的解决方案，我很乐意听听。
抱歉，它是C++，但应该可以翻译。

List * SortList(List * p_list)
{
     if(p_list == NULL || p_list->next == NULL) 
          return p_list;

     List left, right;
     List * piviot = p_list;
     List * piviotEnd = piviot;
     List * next = p_list->next;
     do
     {
              p_list = next;
              next = next->next;
              //FIGURE OUT WHICH SIDE I'M ADDING TO.
              if(p_list->data > piviot->data ) 
                  right.InsertNode(p_list);
              else if(p_list->data < piviot->data)
                  left.InsertNode(p_list);
              else
              {   //we put this in it's own list because it doesn't need to be sorted
                  piviotEnd->next = p_list;
                  piviotEnd= p_list;
              }  
     }while(next);

     //now left contains values < piviot and more contains all the values more
     left.next = SortList(left.next);
     right.next = SortList(right.next);

     //add the piviot to the list then add the rigth list to the full list
     left.GetTail()->next = piviot;
     piviotEnd->next = right.next;

     return left.next;
}
关于您的评论“我怀疑仅仅说使用STL就足够了”- 在面试时，如果没有充分的理由而不选择使用预先准备好的BCL，我会质疑任何人的理智。OP没有说明原因，因此BCL应该是默认选择。 - Marc Gravell
同意。我完全赞成你的专业观点。我从未考虑过实现链表。如果我被面试问到，我也会指出这一点。然而，通常他们想看到你流汗，所以你仍然需要实现它。 - baash05
好的，现在我要和自己的想法不同意一下。--- 我正在编写没有访问STL的代码.. 所以我需要自己创建一个排序器.. 幸运的是我写了这个答案，所以我将使用它.. :) - baash05
0
public LinkedListNode<int> Sort2(LinkedListNode<int> head, int count)
    {
        var cur = head;
        var prev = cur;
        var min = cur;
        var minprev = min;

        LinkedListNode<int> newHead = null;
        LinkedListNode<int> newTail = newHead;

        for (int i = 0; i < count; i++)
        {
            cur = head;
            min = cur;
            minprev = min;

            while (cur != null)
            {
                if (cur.Value < min.Value)
                {
                    min = cur;
                    minprev = prev;
                }
                prev = cur;
                cur = cur.Next;
            }

            if (min == head)
                head = head.Next;
            else if (min.Next == null)
                minprev.Next = null;
            else
                minprev.Next = minprev.Next.Next;

            if (newHead != null)
            {
                newTail.Next = min;
                newTail = newTail.Next;
            }
            else
            {
                newHead = min;
                newTail = newHead;
            }
        }
        return newHead;
    }
0

如果你想真正利用链表的优势，而不是绕过它，我建议使用插入排序。

通常情况下，插入排序效率不高 - 最坏情况下为O(n^2)，但使用链表可以将其提高到O(n log n)

伪代码：

for i in range (1,n):
    item = arr[i]
    location = binary_search(l=root, r=i, value=item.val)  // O(log i)
    insert_item_before(arr[location], item) // O(1)

在常规算法中，插入部分需要O(i)的时间复杂度，因为我们可能需要移动所有大于item的元素。由于链表使我们能够在不移动元素的情况下进行插入操作，我们可以使用二分查找来寻找插入位置，因此插入部分只需要O(log i)的时间复杂度。
注意：通常情况下，插入排序在最好的情况下（数组已经排序）具有O(n)的性能。不幸的是，在这里并非如此，因为二分查找始终需要O(log n)的步骤。
0

这是一个基于插入排序的实现。它应该足够快，适用于较小的链表和/或列表几乎已经排序完毕的情况下。对于大型列表，请查看M.kazem Akhgary的答案（使用快速排序）。

static void Sort<T>(this LinkedList<T> list, IComparer<T> comparer)
{
    var node = list.First;
    while (node != null)
    {
        var next = node.Next;
        
        var min = node;
        for (var comp = node.Previous; 
             comp != null && comparer.Compare(node.Value, comp.Value) < 0; 
             comp = comp.Previous)
        {
            min = comp;
        }
        
        if (node != min) 
        {               
            list.Remove(node);
            list.AddBefore(min, node);
        }
        
        node = next;
    }
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接