java - java双向链表插入排序算法

Question

我有一个带有哨兵节点的双向链表，我需要使用复杂度为 O(n^2) 的插入排序对其进行排序。我已经编写了这段代码，但它没有按预期工作。

对于插入排序，尤其是代码，有什么帮助吗？

    public void insertionSort()
    {
        int key,i;
        int size = getSize();
        this.restart();
        for(i = 2; i < size; i++)
        {
            this.next();  // Go to next node
            key = this.getVar(); // get the integer a node holds
            while(this.hasNext() == 1 && position.prev.var < key && position.var != -1)
            {
                position.prev.setNext(position.next);
                position.next.setPrev(position.prev);
                position.setNext(position.prev);
                position.setPrev(position.prev.prev);
                position.prev.setNext(position);
                position.next.setPrev(position);    
                this.goBack(); // go to the previous node
            }                       
        }

    }

大小是我的列表有多少个元素。我的哨兵有 var = -1，所以我想在我处于领先位置时停止，这就是我使用它的原因。

position.var != -1

并且 this.hasNext() == 1 只要我们位于 !=哨兵节点 的位置，就为真。

在具体示例中，我的列表中有 35 个整数:

5 9 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1

我想这样对它们进行排序:

9 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

更新:我在插入排序中使用的代码如下:

public int getSize()
        {
            int size = 0;
            this.restart();
            while(this.hasNext() == 1)
            {
                size++;
                this.next();
            }
            return size;
        }

public void restart()
        {
            position = header;
            previous = Sentinel;
        }

public void next()
        {
            previous = position;
            position = position.next;
        }

public int getVar()
        {
            return position.var;
        }

public void goBack()
        {
            position = previous;
            previous = previous.prev;
        }

    public int hasNext()
        {
            if(position.var != -1)
                return 1;
            else 
                return 0;
        }

    public void setNext(Node next)
        {
            this.next = next;
        }

public void setPrev(节点上一个) { 这. 上一个 = 上一个; }

此外，我使用列表迭代器。

Answer 1

这是我对内循环的分析笔记，你是对的，那里肯定有问题。

position.unlink():越界，邻居成为直接邻居

position.prev.next = position.next;  // TODO 1: position.next.prev = position.prev
position.next.prev = position.prev;  // TODO 2: position.prev.next = position.next
                  ^  Breaks TODO 1, but we can: position.prev.next.prev = position.prev

所以我们仍然需要 TODO 1，然后是 2，按这个顺序:

     -- TODO 1: position.prev.next.prev = position.prev
     -- TODO 2: position.prev.next      = position.next

position.insertBefore(position.prev):重新排队，排在更靠后的位置

position.next = position.prev;          // TODO 3: position.prev.prev = position
position.prev = a = position.prev.prev; // TODO 4: a.next = position
//           ^                          //   same: position.prev.next = position   
//           |                          // *Error 1!*
//           + breaks TODO's 1 and 2, *Error 2!*
//           + breaks TODO 3, but we can instead: position.next.prev = position

关于错误1，TODO 3和TODO 4都涉及到position.prev，将其next和prev都设置为position ;这有效地包围了 position.prev与位置。无论它前进还是后退，它的直接邻居都是位置。然而迈出一步之后，一切都是一样的。有趣的结构 - 就像你房子的前门和后门都通往同一个地方。

错误 2 导致无法更新 position.prev，这是 TODO 的 1 所需要的、2 和 3。我们仍然可以通过使用通过 position.prev 的 next 访问 a.next 的替代表达式来满足 TODO 3字段，但无法再满足 TODO 的 1 和 2。

position.insertBefore(position.prev)，继续:

position.prev.next = position;        // DONE: 4 
position.next.prev = position;        // DONE: 3 

这两行完成了 TODO 3 和 4，所以剩下的就是:

     -- TODO 1: position.prev.next.prev = position.prev
     -- TODO 2: position.prev.next      = position.next
     -- TODO 5: fix Error 1
     -- TODO 6: fix Error 2

修复错误 1 ​​涉及确保 TODO 1 和 2 在 TODO 4 之前完成，修复错误 2 涉及确保 TODO 3 在分配 a 之前完成。

您最终完成了 8 项作业；事后看来，对于双向链表和涉及 4 个节点的移动来说并不奇怪。