如何使用Java集合LinkedList实现选择排序算法并修复现有代码问题

现有代码的核心问题 #

• 排序逻辑完全不符合选择排序的规则：代码混淆了遍历逻辑，外层迭代器+内层双重for循环属于重复遍历，且没有按照选择排序「每轮锁定未排序区间最小元素，交换到当前已排序区间末尾」的逻辑实现
• swap方法存在致命缺陷：使用indexOf()查找元素索引，遇到重复值时只会返回第一个匹配项的位置，直接导致重复元素的排序出错，比如测试用例中的两个23就会因此排序失败
• 边界判断错误：原swap方法里的判断条件index2== -2属于无效判断，元素不存在时indexOf返回的是-1
• 频繁调用LinkedList.get()方法性能极低：LinkedList是链表结构，随机访问的时间复杂度是O(n)，频繁调用会导致排序效率大幅下降

修复后的完整实现 #

调整swap方法直接传入索引进行交换，避免重复元素的匹配问题；重写sort方法严格按照选择排序逻辑实现：

import java.util.*;
public class SelectSort {
    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) {
        int n = data.size();
        // 外层循环：标记已排序区间的末尾位置
        for (int i = 0; i < n - 1; i++) {
            // 记录未排序区间最小元素的索引
            int minIndex = i;
            // 内层循环：遍历未排序区间找最小元素的位置
            for (int j = i + 1; j < n; j++) {
                if (data.get(j) < data.get(minIndex)) {
                    minIndex = j;
                }
            }
            // 把找到的最小元素交换到已排序区间的末尾
            swap(data, i, minIndex);
        }
        return data;
    }

    // 直接传入索引交换，避免重复元素匹配错误
    private static void swap(LinkedList<Integer> data, int index1, int index2) {
        if (index1 == index2) {
            return;
        }
        int temp = data.get(index1);
        data.set(index1, data.get(index2));
        data.set(index2, temp);
    }
}

优化说明 #

如果要进一步提升LinkedList排序性能，可以将随机访问的get方法替换为迭代器遍历定位元素，避免每次get都从头遍历链表，更适合数据量较大的使用场景。

内容的提问来源于stack exchange，提问作者Maria Marchella Gandhi