对链表进行排序

我在C＃中编写了一个基本的链表类。 它有一个Node对象，它（显然）代表列表中的每个节点。

代码不使用IEnumerable，但是，我可以实现排序function吗？ 我使用的语言是C＃。 在C＃中有这样的例子吗？

我正在使用这个样本 ：

谢谢

Answer 1

function性Quicksort和Mergesort

这是一个链接列表，其中包含以函数样式编写的quicksort和mergesort方法：

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 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); } } 

使用配对堆的function性堆

奖励：heapsort（使用function配对堆）。

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

针对链表的势在必行的Quicksort

要求提供就地版本。 这是一个非常快速的实现。 我从上到下编写了这段代码而没有寻找使代码更好的机会，即每一行都是我想到的第一行。 它非常难看，因为我使用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)); 

神奇地它第一次工作！ 我很确定这段代码包含错误。 不要责怪我。

 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); } } 

Answer 2

当然，您可以使用纯链接列表实现排序function。 合并排序可能是一个合适的算法，它很简单。

Answer 3

最简单的选择可能是提取数据，在已经支持排序的机制（数组， List或IEnumerable通过LINQ）中对数据进行排序，并使用排序数据重新构建链表。

如果您想编写自己的排序算法，那么您可能会发现Comparer.Default很有用（假设您使用的是generics）。 这应该允许您比较IComparable或IComparable任何项目。

另外请注意，.NET已经包含LinkedList等; 如果这只是为了学习等，那么很好;-p

Answer 4

这可能不是最好的解决方案，但它就像我能想到的一样简单。 如果有人能想到更简单但仍然快的东西，我很乐意听到它。
抱歉它是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; } 

Answer 5

有些人（包括我）可能想要从.net库中对LinkedList进行排序。

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

对于需要某种程度优化的人来说，这里是针对.net双向链表的通用就地快速排序实现。

此实现不会拆分/合并，而是检查节点以查找每个递归的边界。

 /// 
 /// in place linked list sort using quick sort. /// 
 public static void QuickSort(this LinkedList linkedList, IComparer comparer) { if (linkedList == null || linkedList.Count <= 1) return; // there is nothing to sort SortImpl(linkedList.First, linkedList.Last, comparer); } private static void SortImpl(LinkedListNode head, LinkedListNode tail, IComparer comparer) { if (head == tail) return; // there is nothing to sort void Swap(LinkedListNode a, LinkedListNode 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); } 

Answer 6

 for(int i=0; icurrent.next.element) { Swap(current.elment,current.next.element); } current=current.next; } } 

向链接列表添加或插入元素时的增量计数器

Answer 7

如果你想真正利用你使用链表的事实，而不是解决它，我会建议插入排序。

通常情况下，插入排序不是很有效 – 在最坏的情况下是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所有item 。 因为链接列表使我们可以在不移动的情况下进行插入，我们可以使用二进制搜索来搜索位置，因此插入部分只需要O(log i)

注意：通常，插入排序在最佳情况下具有O(n)性能（如果数组已排序）。 不幸的是，这不是这种情况，因为二进制搜索总是采用O(log n)步骤。

Answer 8

 public LinkedListNode Sort2(LinkedListNode head, int count) { var cur = head; var prev = cur; var min = cur; var minprev = min; LinkedListNode newHead = null; LinkedListNode 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; }