插入排序实现问题：原列表显示为排序结果，如何修正？

你的问题核心在于：插入排序方法是对传入的ArrayList进行原地修改，而你在代码中先调用了排序方法，再打印"原列表"，此时原列表已经被排序算法修改，自然无法输出原始数据。

两种解决思路 #

思路1：调整打印顺序（最简单） #

先打印原始列表，再执行排序，最后打印排序后的列表：

import java.util.ArrayList;
public class InsertionSort<E extends Comparable<E>> {
  
    public void insertionSort(ArrayList<E> list) {
        int n = list.size();
        for (int i = 1; i < n; i++) {
            E key = list.get(i);
            int j = i - 1;
            while (j >= 0 && list.get(j).compareTo(key) > 0) {
                list.set(j + 1, list.get(j));
                j--;
            }
            list.set(j + 1, key);
        }
    }

    public static void main(String[] args) {
        int[] test1 = {3, 5, 2, 4, 1, 8, 7, 6, 9};
        double[] test2 = {1.99, 2.05, 9.01, 6.49, 3.14, 5.55};
        char[] test3 =  "algorithm".toCharArray();

        // Test 1
        ArrayList<Integer> list1 = new ArrayList<>();
        for (int num : test1) {
            list1.add(num);
        }
        System.out.println("Test Example 1");
        System.out.println("Original List: " + list1); // 先打印原列表
        InsertionSort<Integer> integerSorter = new InsertionSort<>();
        integerSorter.insertionSort(list1); // 再执行排序
        System.out.println("Sorted List: " + list1); // 打印排序后的列表
  
        // Test 2
        ArrayList<Double> list2 = new ArrayList<>();
        for (double num : test2) {
            list2.add(num);
        }
        System.out.println("\nTest Example 2");
        System.out.println("Original List: " + list2);
        InsertionSort<Double> doubleSorter = new InsertionSort<>();
        doubleSorter.insertionSort(list2);
        System.out.println("Sorted List: " + list2);

        // Test 3
        ArrayList<Character> list3 = new ArrayList<>();
        for (char ch : test3) {
            list3.add(ch);
        }
        System.out.println("\nTest Example 3");
        System.out.println("Original List: " + list3);
        InsertionSort<Character> charSorter = new InsertionSort<>();
        charSorter.insertionSort(list3);
        System.out.println("Sorted List: " + list3);
    }
}

思路2：保留原列表副本（适合后续需使用原数据的场景） #

创建原列表的副本，对副本执行排序，原列表保持不变：

import java.util.ArrayList;
public class InsertionSort<E extends Comparable<E>> {
  
    public void insertionSort(ArrayList<E> list) {
        int n = list.size();
        for (int i = 1; i < n; i++) {
            E key = list.get(i);
            int j = i - 1;
            while (j >= 0 && list.get(j).compareTo(key) > 0) {
                list.set(j + 1, list.get(j));
                j--;
            }
            list.set(j + 1, key);
        }
    }

    public static void main(String[] args) {
        int[] test1 = {3, 5, 2, 4, 1, 8, 7, 6, 9};
        double[] test2 = {1.99, 2.05, 9.01, 6.49, 3.14, 5.55};
        char[] test3 =  "algorithm".toCharArray();

        // Test 1
        ArrayList<Integer> originalList1 = new ArrayList<>();
        for (int num : test1) {
            originalList1.add(num);
        }
        ArrayList<Integer> sortedList1 = new ArrayList<>(originalList1); // 复制原列表
        InsertionSort<Integer> integerSorter = new InsertionSort<>();
        integerSorter.insertionSort(sortedList1); // 对副本排序
        System.out.println("Test Example 1");
        System.out.println("Original List: " + originalList1);
        System.out.println("Sorted List: " + sortedList1);
  
        // Test 2
        ArrayList<Double> originalList2 = new ArrayList<>();
        for (double num : test2) {
            originalList2.add(num);
        }
        ArrayList<Double> sortedList2 = new ArrayList<>(originalList2);
        InsertionSort<Double> doubleSorter = new InsertionSort<>();
        doubleSorter.insertionSort(sortedList2);
        System.out.println("\nTest Example 2");
        System.out.println("Original List: " + originalList2);
        System.out.println("Sorted List: " + sortedList2);

        // Test 3
        ArrayList<Character> originalList3 = new ArrayList<>();
        for (char ch : test3) {
            originalList3.add(ch);
        }
        ArrayList<Character> sortedList3 = new ArrayList<>(originalList3);
        InsertionSort<Character> charSorter = new InsertionSort<>();
        charSorter.insertionSort(sortedList3);
        System.out.println("\nTest Example 3");
        System.out.println("Original List: " + originalList3);
        System.out.println("Sorted List: " + sortedList3);
    }
}

内容的提问来源于stack exchange，提问作者williamj987