这是一个使用快速排序和mergeesort方法编写的功能样式的链表：

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

使用配对堆的功能性堆肥

奖金：heapsort(使用功能配对堆).

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