1

所以我试图让我的双链表做一个插入排序

我现在遇到问题，只是将节点移动到正确的位置。我已经进行了比较，但我的节点都没有移动。

public void insertionSort()
{
    Node temp;
    Node start = this.head.next;
    Node next = start.next;
    Node prev = this.head;

    while(start != this.head)
    {
        if(start.data.compareTo(next.data) > 0) //start is larger than next
        {
            temp = start;
            start = next;
            next = temp;
        }
        start = start.next;
        next = next.next;
        prev = prev.next;
    }
}

我想知道是否有人可以帮助我正确使用此算法。我正在使用循环双向链表来尝试测试各种排序例程的时间复杂度。

4

1 回答 1

0

有趣的谜题！

我可以看到你的算法的主要问题是你只给被插入的节点有机会向后移动一个位置。

插入排序从列表中的第二个节点逐个查找到最后一个节点，将它们向后交换，直到它们在前面已经排序的列表中排序。这可能需要多次交换，但您的算法只允许一个（当您的 if 条件为真时）或零（当它为假时）。例如，假设我们正在排序：

bca

start当位于 b 和 c时，您的插入排序将起作用，然后它会移动到 a。在这里你说'如果a在c之前，用c交换'，给出：

背书

...但是您的算法将终止。由于您需要为每个插入的节点执行未确定数量的交换，因此您需要另一个 while 循环。下面是插入排序算法的伪代码：

function insertion_sort(items) {
    while (i=1; i < items length; i++) { // for elements 1 to n
        while (j=i; j >= 0; j--) { // look backward through all previously sorted items
            if (items element at j < items element at j-1) {
                 swap element at j with element at j-1
            } else {
                break out of the loop
            }
        }
    }
}
于 2012-10-18T04:55:57.650 回答