排序链表 [英] Sorting a linked list
问题描述
我已经用C＃编写一个基本的链表类。它有一个Node对象，（显然）重新presents每个节点在列表中。
I have written a basic linked list class in C#. It has a Node object, which (obviously) represents every node in the list.
在code不使用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#?
我是从这个<工作href="http://www.c-sharpcorner.com/UploadFile/jeradus/UsingLinkedListInCS11102005005525AM/UsingLinkedListInCS.aspx">sample:
感谢
推荐答案
下面是一个链表写在功能性风格的快速排序和归并方法：
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)));
势在必行就地快速排序的链表
这是就地被请求的版本。这里有一个非常快速的实现。我写这篇code从上到下没有寻找机会，使code更好，即每行是浮现在脑海的第一线。这是因为我用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.
此外我测试了code上的一个例子：
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));
神奇，它的工作的第一次！我是pretty的肯定，这code中的bug，虽然。请不要把我的责任。
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屋！
