排序链表 [英] Sorting a linked list
本文介绍了排序链表的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
代码不使用IEnumerable，但是我可以实现排序功能吗？我使用的语言是C＃。在C＃中有一个例子吗？
我正在从这个示例：
谢谢
解决方案
功能Quicksort和Mergesort
这是一个使用功能样式编写的quicksort和mergesort方法的链接列表：
类列表
{
public int item;
public List rest;
public List（int item，List rest）
{
this.item = item;
this.rest = rest;
}
// 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）
else if（p（xs.item））返回新的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））;
列表more = QSort（Filter（x => x> pivot，xs.rest））;
return附加（少，新List（pivot，more））;
}
}
// mergeesort的助手方法
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）返回新的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;
列表left = MSort（Take（len，xs））;
列表权限= MSort（Drop（len，xs））;
返回合并（左，右）;
}
}
public static string Show（List xs）
{
if（xs == null）return;
else return xs.item.ToString（）++ Show（xs.rest）;
}
}
使用配对堆的功能堆栈
奖金：heapsort（使用功能配对堆）。
类列表
{
// ...
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
{
剩下的堆;
int min;
堆右
public Heap（Hele 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;
堆小= a.min< = b.min？ a：b
堆大= a.min <= b.min？ b：a
返回新堆（small.left，smaller.min，Merge（smaller.right，greater））;
}
public static Heap DeleteMin（aap a）
{
return Merge（a.left，a.right）;
}
public static List Heap2List（heap a）
{
if（a == null）return null;
else返回新列表（a.min，Heap2List（DeleteMin（a）））;
}
}
对于实际使用，您要重写帮助程序，而不需要使用递归，并可能使用可变列表，如内置的。
如何使用：
列表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作为空列表:)缩进不一致等。
此外，我只测试了一个例子：
$ （4，new MList（2，new MList（3，new MList（1，null））））; b$ b
MList ys = new MList
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;
//将列表分成两部分
MList smaller = null; // items than pivot
MList greater = null; //项目大于pivot
while（xs！= null）
{
var rest = xs.rest;
if（xs.item< pivot）{
xs.rest = smaller;
smaller = xs;
} else {
xs.rest = greater;
greater = xs;
}
xs = rest;
}
//排序越来越小的列表
QSortInPlace（ref small）;
QSortInPlace（ref大）;
// append small + [pivot] + greater
AppendInPlace（ref pivotNode，greater）;
AppendInPlace（ref small，pivotNode）;
xs =较小;
}
public static void AppendInPlace（ref MList xs，MList ys）
{
if（xs == null）{
xs = ys;
return;
}
//找到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）;
}
}
I have written a basic linked list class in C#. It has a Node object, which (obviously) represents every node in the list.
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#?
I am working from this sample:
Thanks
解决方案
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.
How to use:
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)));
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屋！
查看全文
