如何使用 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;
        }
    }
}

排序后的数据总是和原始数据一样，不知道哪里出错了。

编辑：swap 方法现在可以完美运行，但数据的顺序仍然不正确。

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 方法总是 returns 索引，如果找到，或者 -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;
}

如何使用 Java 集合链表进行选择排序算法？

How to make a selection sort algorithm using Java collection linkedlist?

java

interface

linked-list

selection-sort