如何使用Java集合链表制作选择排序算法

Question

我是Java新手，需要使用Java LinkedList来制定选择排序算法。我尝试进行插入排序，但无法将其转换为选择排序。这是我的选择排序代码：

import java.util.*;
public class select {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
LinkedList<Integer> data = new LinkedList<>();
System.out.println("Enter total count of elements-> ");
int num = input.nextInt();
while(num>0){
data.add(input.nextInt());
num--;
}
System.out.println("Original data:n" +data);
LinkedList<Integer> sortedData=sort(data);
System.out.println("Sorted data:n"+sortedData);
}

public static LinkedList<Integer> sort(LinkedList<Integer> data) {

ListIterator<Integer> iterator=data.listIterator();
while (iterator.hasNext()) {
int key=iterator.next();

for(int i = 0 ;i<data.size()-1;i++) {
for(int j = i+1; j < data.size(); j++){
if(data.get(j) < key){
int x = data.get(j);
int y = key;
swap(data, x, y);
}
}

}
}
return data;
}
private static void swap(LinkedList<Integer> data, int x, int y) {
int index1 = data.indexOf(x);
int index2 = data.indexOf(y);
if(index1 == -1 || index2== -2){
return;
}
}
}

排序后的数据总是与原始数据相同，我不知道哪一个出错了。

编辑：交换方法现在可以完美地工作，但数据的顺序仍然不正确。

Original data:
[23, 12, 6, 23, 98]
Sorted data:
[12, 6, 23, 98, 23]

所以我想排序方法就是问题所在。

Answer 1

要解决输出不更改的问题：swap方法实际上不交换值。

正如您所期望的，这两行将获得您的数据索引。

int index1 = data.indexOf(x);
int index2 = data.indexOf(y);

但所有这些都是为了确保你的索引是有效的，这意味着数据是被找到的。(尽管第二个检查也应该是-1，因为#indexOf方法总是返回索引(如果找到(或-1。从不-2.(

if (index1 == -1 || index2 == -1){ // changed to -1 on both
return;
}

要真正进行交换，您需要在swap方法中的其他代码末尾这样的东西：

data.set(index1, y);
data.set(index2, x);

#set方法将第一个参数索引处的值更改为第二个参数中的值，因此这样做两次将有效地交换数据。

为了解决代码排序不正确的问题：您使用ListIterator和while循环来循环列表，这意味着您不必递增地检查每个数字及其后的数字，而是重复检查第一个数字及其后，这在第一次通过后不会起任何作用。

ListIterator<Integer> iterator=data.listIterator();
while (iterator.hasNext()) { // This will loop through the list once overall
int key=iterator.next(); // This is the current item of the while loop
for(int i = 0 ;i<data.size()-1;i++) { // This loop is completely ignored
for(int j = i+1; j < data.size(); j++){
if(data.get(j) < key){ // You are comparing to key, which is just the item in the overall list iteration
int x = data.get(j);
int y = key;
swap(data, x, y);
}
}          
}
}

您没有从外部for循环使用i，因为您使用的是key。要解决这个问题，您应该完全删除while循环和迭代器：

public static LinkedList<Integer> sort(LinkedList<Integer> data) {
for(int i = 0 ;i<data.size()-1;i++) {
for(int j = i+1; j < data.size(); j++){
int x = data.get(j); // Another optimization you can make is to only call the `#get` method once for each index, like this
int y = data.get(i);
if(x < y){
swap(data, x, y);
}
}
}
return data;
}