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

和这个。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

UPDATE：我在插入排序中使用的代码如下：

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（Node prev）{this.prev=prev；}

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

Answer 1

这应该可以解决问题：

        int j;
        // ...
        for(i = 1; i < size; i++)
        {
            this.restart();          // start at ith node
            for(j = 0; j < i; j++)
                this.next();
            key = this.getVar();     // same code as before

或者使用另一个变量，该变量在每个外部循环中一次前进一个节点。

还有，这不应该。hasNext（）将重命名为此。hasPrev（）？

代码的主要部分似乎正确，示例图：

                // goal: swap B and C
                // initial state
          p        
    -> -> -> ->
    A  B  C  D
   <- <- <- <-
                // remove C from list
                position.prev.setNext(position.next);
                position.next.setPrev(position.prev);
          p
       ----->
    ->    -> ->
    A  B  C  D
   <- <- <-
         <----
                // update C next and previous                    
                position.setNext(position.prev);
                position.setPrev(position.prev.prev);
       p
    ----->
       -> -> ->
    A  C  B  D
   <- <-    <-
      <----
                // insert C into list
                position.prev.setNext(position);
                position.next.setPrev(position);
       p
    -> -> -> ->
    A  C  B  D
   <- <- <- <-

Answer 2

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

位置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.insert前（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，将它的下一个和前设置为位置；这有效地包围了position.prev用位置。无论前进还是后退，它的直接邻居都将是位置。然而，一步之后，一切都是一样的。有趣的结构——就像你房子的前门和后门都通向同一个地方。

错误2导致无法更新位置。prev，这是TODO的1、2和3所需的。通过使用另一个表达式访问a.next到位置，我们仍然可以满足TODO 3的要求。上一个的下一个字段，但TODO的1和2不能再满足。

position.insert之前（position.prev），继续：

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

这两行完成了TODO 3和TODO 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个节点的运动来说，这并不奇怪。