对链表进行排序 [英] Sorting a linked list
问题描述
我用 C# 编写了一个基本的链表类.它有一个 Node 对象，它(显然)代表列表中的每个节点.
I have written a basic linked list class in C#. It has a Node object, which (obviously) represents every node in the list.
代码没有使用IEnumerable，但是可以实现排序功能吗?我使用的语言是 C#.在 C# 中有这样的例子吗?
The code does not use IEnumerable, however, can I implement a sorting function? The language I am using is C#. Is there an example of this in C#?
我正在使用这个示例:
谢谢
推荐答案
Functional Quicksort and Mergesort
这是一个以函数式风格编写的带有快速排序和归并排序方法的链表:
Functional Quicksort and Mergesort
Here's a linked list with quicksort and mergesort methods written in a functional style:
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);
}
}
使用配对堆的函数式堆排序
奖励:堆排序(使用功能配对堆).
Functional heapsort using a Pairing Heap
Bonus: heapsort (using functional pairing heap).
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)));
}
}
在实际使用中，您希望在不使用递归的情况下重写辅助方法，并且可能使用像内置列表那样的可变列表.
For actual use you want to rewrite the helper methods without using recursion, and maybe use a mutable list like the built-in one.
使用方法:
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作为空列表:)缩进不一致等
Imperative In-place Quicksort for linked lists
An in-place version was requested. Here's a very quick implementation. I wrote this code top to bottom without looking for opportunities to make the code better, i.e. every line is the first line that came to mind. It's extremely ugly because I used null as the empty list :) The indentation is inconsistent, etc.
此外，我仅在一个示例上测试了此代码:
Additionally I tested this code on only one example:
MList ys = new MList(4, new MList(2, new MList(3, new MList(1, null))));
MList.QSortInPlace(ref ys);
Console.WriteLine(MList.Show(ys));
神奇的是它第一次就成功了！我很确定这段代码包含错误.不要让我负责.
Magically it worked the first time! I'm pretty sure that this code contains bugs though. Don't hold me accountable.
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);
}
}
这篇关于对链表进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
