我的 SelectionSort 方法不起作用。为什么？
我正在尝试在我自己编写的双向链表版本中使用选择排序算法。对于这个问题，我们可以假设除了我发布的代码之外，其他地方没有错误（至少没有与问题相关的错误）。我已经做了很多测试。
这是我的方法：
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 行收到空指针之前的最后一位输出（已标记）。
交换95,97
a：96 我：97 i: 98
交换96,97
a: 97 i: 98
交换97,97
a: 98 我：99 （空指针）
我之前就已经完成了这个工作，但它经过了可怕的优化。做了一些改变后，我坚持了下来。有什么想法吗？
感谢您抽出时间。
I am trying to use the selection sort algorithm in a version of the doubly linked list that I wrote myself. For this question we can assume that there are no errors elsewhere other than the code that I post (at least, none relevant to the question). I have done plenty of testing.
here is my method:
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);
}
}
It is sorting a list of 100 integers. Here is the last bit of output before I receive a null pointer on line 29 (marked).
swapped95,97
a: 96
i: 97
i: 98
swapped96,97
a: 97
i: 98
swapped97,97
a: 98
i: 99
(null pointer)
I had this working earlier but it was horribly optimized. After making some changes, I'm stuck with this. Any ideas?
Thanks for your time.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
好吧，您正在尝试访问 null 元素的内容。当您位于最后一个元素时，当您将其设置为下一个时，“当前”将为空。
我想我有点太累了，无法提供修复程序，但是您应该能够将旧的（工作）代码与它进行比较并找到修复程序。
Well you're trying to access the content of a null element. When you're on the last element, your "current" will null when you set it to next.
I think I'm a little too tired to provide a fix for it, but you should be able to compare your old (working) code to it and spot the fix.
我认为问题可能出现在排序循环的第一次迭代中。考虑到此函数中的第一行 (
ListItem front = head) 将front指向列表的第一个元素，似乎可以通过调用：front = front 。下一个;当前=前面.下一个;您实际上“跳过”列表中索引 1 处的元素，并开始索引 2 处元素的比较循环。例如，如果您的（未排序）列表如下所示：
[54, 11, 25, 34]它看起来像
[25, 11, 54, 34]在排序算法第一次迭代之后， 。由于下一次迭代将从索引 1 开始，因此元素 11 永远不会被放置在索引 0 处，即使它是列表中的最低元素。
可能正是这种不准确导致了列表末尾的空指针问题。我会考虑将语句
front = front.next;放在内部 for 循环之后 和swap(a, lowerIndex) 之前 ;声明。这将防止第一次迭代中可能出现的错误，并可能解决您的问题。I think the problem might arise in the first iteration of your sorting loop. Considering the first line in this function (
ListItem front = head) points thefrontto the first element of the list, it seems that by calling:front = front.next; current = front.next;you actually 'skip' the element at index 1 in the list and start your comparison loop of the element at index 2.For example, if your (unsorted) list looks like this:
[54, 11, 25, 34]It will look like
[25, 11, 54, 34]after the first iteration of your sorting algorithm. Since the next iteration will start at index 1, the element 11 will never be placed at index 0 even though it is the lowest element in the list.
It might be this inaccuracy which causes the null pointer problem at the end of the list. I would consider putting the statement
front = front.next;after the inner for loop and before theswap(a, lowestIndex);statement. This will prevent the possible error in the first iteration and might solve your problem.