单向链表的插入排序 [外部]

Question

我不确定从哪里开始，但这很混乱。基本上我需要为单链表编写一个插入排序方法——这会导致足够多的问题，因为通常对于插入排序——你应该向后遍历 array/list 个元素——将其实现到单链表中似乎毫无意义，因为它的重点 - 是你只能在列表中前进，除此之外 -> 我需要在外部执行 "swap" 操作，我不完全理解如何在使用时执行它列表结构。

这是我使用的 ArrayClass 和 Swap 方法：

class MyFileArray : DataArray
{
    public MyFileArray(string filename, int n, int seed)
    {
        double[] data = new double[n];
        length = n;
        Random rand = new Random(seed);
        for (int i = 0; i < length; i++)
        {
            data[i] = rand.NextDouble();
        }
        if (File.Exists(filename)) File.Delete(filename);
        try
        {
            using (BinaryWriter writer = new BinaryWriter(File.Open(filename,
           FileMode.Create)))
            {
                for (int j = 0; j < length; j++)
                    writer.Write(data[j]);
            }
        }
        catch (IOException ex)
        {
            Console.WriteLine(ex.ToString());
        }
    }
    public FileStream fs { get; set; }
    public override double this[int index]
    {
        get
        {
            Byte[] data = new Byte[8];
            fs.Seek(8 * index, SeekOrigin.Begin);
            fs.Read(data, 0, 8);
            double result = BitConverter.ToDouble(data, 0);
            return result;
        }
    }
    public override void Swap(int j, double a)
    {
        Byte[] data = new Byte[16];
        BitConverter.GetBytes(a).CopyTo(data, 0);
        fs.Seek(8 * (j + 1), SeekOrigin.Begin);
        fs.Write(data, 0, 8);
    }
}

这是我的数组插入排序：

public static void InsertionSort(DataArray items)
    {
        double key;
        int j;
        for (int i = 1; i < items.Length; i++)
        {
            key = items[i];
            j = i - 1;
            while (j >= 0 && items[j] > key)
            {
                items.Swap(j, items[j]);
                j = j - 1;
            }
            items.Swap(j, key);

        }
    }

现在我不得不以某种方式做完全相同的事情 - 但是使用单链表，我得到了这种 class 来处理（允许进行更改）：

class MyFileList : DataList
{
    int prevNode;
    int currentNode;
    int nextNode;
    public MyFileList(string filename, int n, int seed)
    {
        length = n;
        Random rand = new Random(seed);
        if (File.Exists(filename)) File.Delete(filename);
        try
        {
            using (BinaryWriter writer = new BinaryWriter(File.Open(filename,
           FileMode.Create)))
            {
                writer.Write(4);
                for (int j = 0; j < length; j++)
                {
                    writer.Write(rand.NextDouble());
                    writer.Write((j + 1) * 12 + 4);
                }
            }
        }
        catch (IOException ex)
        {
            Console.WriteLine(ex.ToString());
        }
    }
    public FileStream fs { get; set; }
    public override double Head()
    {
        Byte[] data = new Byte[12];
        fs.Seek(0, SeekOrigin.Begin);
        fs.Read(data, 0, 4);
        currentNode = BitConverter.ToInt32(data, 0);
        prevNode = -1;
        fs.Seek(currentNode, SeekOrigin.Begin);
        fs.Read(data, 0, 12);
        double result = BitConverter.ToDouble(data, 0);
        nextNode = BitConverter.ToInt32(data, 8);
        return result;
    }
    public override double Next()
    {

        Byte[] data = new Byte[12];
        fs.Seek(nextNode, SeekOrigin.Begin);
        fs.Read(data, 0, 12);
        prevNode = currentNode;
        currentNode = nextNode;
        double result = BitConverter.ToDouble(data, 0);
        nextNode = BitConverter.ToInt32(data, 8);
        return result;
    }

老实说——我不确定我应该如何实现插入排序，也不确定如何将其转换为外部排序。我以前使用此代码进行非外部排序：

       public override void InsertionSort()
    {
        sorted = null;
        MyLinkedListNode current = headNode;
        while (current != null)
        {
            MyLinkedListNode next = current.nextNode;
            sortedInsert(current);
            current = next;
        }
        headNode = sorted;
    }

    void sortedInsert(MyLinkedListNode newnode)
    {
        if (sorted == null || sorted.data >= newnode.data)
        {
            newnode.nextNode = sorted;
            sorted = newnode;
        }
        else
        {
            MyLinkedListNode current = sorted;
            while (current.nextNode != null && current.nextNode.data < newnode.data)
            {
                current = current.nextNode;
            }
            newnode.nextNode = current.nextNode;
            current.nextNode = newnode;
        }
    }

因此，如果有人可以提供某种 tips/explanations - 或者如果您曾经尝试过这个 - 如何解决此类问题的代码示例，我们将不胜感激！

Answer 1

我实际上最近才解决这个问题。

这是您可以试用的代码示例，它应该开箱即用。

public class SortLinkedList {

 public static class LinkListNode {
    private Integer value;
    LinkListNode nextNode;

    public LinkListNode(Integer value, LinkListNode nextNode) {
        this.value = value;
        this.nextNode = nextNode;
    }

    public Integer getValue() {
        return value;
    }

    public void setValue(Integer value) {
        this.value = value;
    }

    public LinkListNode getNextNode() {
        return nextNode;
    }

    public void setNextNode(LinkListNode nextNode) {
        this.nextNode = nextNode;
    }

    @Override
    public String toString() {
        return this.value.toString();
    }
}

public static void main(String...args) {
    LinkListNode f = new LinkListNode(12, null);
    LinkListNode e = new LinkListNode(11, f);
    LinkListNode c = new LinkListNode(13, e);
    LinkListNode b = new LinkListNode(1, c);
    LinkListNode a = new LinkListNode(5, b);
    print(sort(a));
}


public static void print(LinkListNode aList) {
    LinkListNode iterator = aList;
    while (iterator != null) {
        System.out.println(iterator.getValue());
        iterator = iterator.getNextNode();
    }
}

public static LinkListNode sort(LinkListNode aList){
    LinkListNode head = new LinkListNode(null, aList);
    LinkListNode fringePtr = aList.getNextNode();
    LinkListNode ptrBeforeFringe = aList;
    LinkListNode findPtr;
    LinkListNode prev;
    while(fringePtr != null) {
        Integer valueToInsert = fringePtr.getValue();
        findPtr = head.getNextNode();
        prev = head;
        while(findPtr != fringePtr) {
            System.out.println("fringe=" + fringePtr);
            System.out.println(findPtr);
            if (valueToInsert <= findPtr.getValue()) {
                LinkListNode tmpNode = fringePtr.getNextNode();
                fringePtr.setNextNode(findPtr);
                prev.setNextNode(fringePtr);
                ptrBeforeFringe.setNextNode(tmpNode);
                fringePtr = ptrBeforeFringe;
                break;
            }
            findPtr = findPtr.getNextNode();
            prev = prev.getNextNode();
        }
        fringePtr = fringePtr.getNextNode();
        if (ptrBeforeFringe.getNextNode() != fringePtr) {
            ptrBeforeFringe = ptrBeforeFringe.getNextNode();
        }
    }
    return head.getNextNode();
 }
}

从高层次上看，您正在做的是跟踪边缘 ptr，并插入节点 s.t。它位于相应子列表中的正确位置。

例如，假设我有这个 LL。

3->2->5->4

第一次迭代，我有 fringePtr 在 2，我想在边缘 ptr 之前的子列表中的某个地方插入 2，所以我基本上从 head 开始遍历到边缘 ptr 直到值小于当前值。我还有一个之前跟踪的前一个 ptr（为了解决空值，我在遍历开始时有一个哨兵节点，所以我可以将它插入到头部）。

然后，当我看到它小于当前时，我知道我需要将它插入到前一个的旁边，所以我必须：

使用一个临时指针来跟踪我以前的当前下一个。
将 previuos 绑定到我的 toInsert 节点旁边。
将我的 toInsert 节点绑定到我的临时节点旁边。

然后，要继续，您只需推进 fringe ptr 并重试，基本上构建一个子列表，该子列表在您移动时进行排序，直到 fringe 到达终点。

即迭代看起来像

1. 3->2->5->4
      ^
2. 2->3->5->4
         ^
3. 2->3->5->4
            ^
4. 2->3->4->5 FIN.

单向链表的插入排序 [外部]

Insertion Sort for Singly Linked List [EXTERNAL]

sorting

insertion-sort

external-sorting

singly-linked-list