我的SelectionSort方法不起作用.为什么

Question

我正试图在我自己编写的双重链表的一个版本中使用选择排序算法。对于这个问题，我们可以假设除了我发布的代码之外，其他地方没有错误(至少，没有与问题相关的错误)。我已经做了大量的测试。

下面是我的方法:

public void selectionSort(){
    ListItem front = head;
    ListItem current;
    T currentLowest;
    T potentialLowest;
    int lowestIndex = 0;
    for (int a = 0; a<count-1; a++){
        System.out.println("a: "+a);
        currentLowest = (T) front.content;
        front = front.next;
        current = front.next;
    for(int i = a+1; i<count; i++){
        System.out.println("i: "+i);
**(29)**    potentialLowest = (T) current.content;
        if (potentialLowest.compareTo(currentLowest)==-1)
        {
            currentLowest = (T) current.content;
            lowestIndex = i;
        }
        if(current.next == null)break;
        current = current.next;
    }
    System.out.println("swapped"+a+","+lowestIndex);
    swap(a, lowestIndex);
}

}

正在排序一个包含100个整数的列表。这是在第29行(已标记)收到空指针之前的最后一位输出。

97

swapped95

: 96我:97我:98

97

swapped96

: 97我:98

97

swapped97

: 98我:99(空指针)

我之前有这个工作，但它是可怕的优化。在做了一些改变之后，我被困住了。什么好主意吗?

感谢您的宝贵时间。

Answer 1

你正在尝试访问一个null元素的内容。当你在最后一个元素上时，当你将"current"设置为next时，它将为空。

我想我有点累了，不能为它提供一个修复，但是你应该能够比较你的旧(工作)代码和它，发现修复。

Answer 2

我认为问题可能出现在排序循环的第一次迭代中。考虑到该函数的第一行(ListItem front = head)将front指向列表的第一个元素，似乎通过调用:front = front.next; current = front.next; ，您实际上"跳过"列表中索引1处的元素，并开始对索引2处的元素进行比较循环。

例如，如果你的(未排序的)列表是这样的:

[54, 11, 25, 34]

它看起来像

[25, 11, 54, 34]

在排序算法的第一次迭代之后。由于下一次迭代将从索引1处开始，因此元素11永远不会被放置在索引0处，即使它是列表中最低的元素。

可能正是这种不准确性导致了列表末尾的空指针问题。我会考虑将语句front = front.next; 放在内部for循环之后，并将放在 swap(a, lowestIndex);语句之前。这将防止在第一次迭代中可能出现的错误，并可能解决您的问题。