数组链接列表插入排序

Question

我必须做一个插入排序的数组列表，我的老师把它发回给我并给了我一个F，但说我可以在星期五之前弥补。我不明白为什么这不是 A.L 插入排序。有人可以帮我解决这个问题，让它符合他的标准吗？谢谢。

他说：

检查您的第一个插入排序后，你们都做错了。我特别说要移动数字并将数字移动到适当的位置，而不是将数字交换到位。在MySA的作业中，我说如果你这样做，你会得到0的作业。

 import java.util.ArrayList;
 public class AListINSSORT {
     private static void insertionSort(ArrayList<Integer> arr) {
          insertionSort();
     }
     private static void insertionSort() {
        ArrayList<Integer> swap = new ArrayList<Integer>();
        swap.add(1);
        swap.add(2);
        swap.add(3);
        swap.add(4);
        swap.add(5);
        int prior = 0;
        int latter = 0;
        for (int i = 2; i <= latter; i++)
        {
            for (int k = i; k > prior && (swap.get(k - 1) < swap.get(k - 2)); k--)  
            {
                Integer temp = swap.get(k - 2);
                swap.set(k - 2, swap.get(k - 1));
                swap.set(k - 1, temp);
            }
        }
        System.out.println(swap);
    }
 }

Answer 1

首先，你的老师似乎要求你使用LinkedList而不是ArrayList。它们之间有很大的区别。

其次，也许更切中要害。在内部循环中，您正在保存一个临时变量，并将位置 k - 2 和 k - 1 的元素相互交换。从评论来看，这不是你老师的本意。由于他希望您解决元素插入的问题，因此我建议您查看以下LinkedList.add（int i，E e）的方法定义：https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html#add（int，%20E）。

这应该为您指明正确的方向。

Answer 2

据我所知，您的代码根本不做任何事情。外部 for 回路的状况

for (int i = 2; i <= latter; i++)

未实现。

当你从i = 2开始，就像latter = 0一样，它永远不会i <= latter。因此，您永远不会运行外部 for 循环，最后只是返回输入值。

如果以不同的顺序（尚未排序）将输入值添加到swap，您将看到代码不会对它们重新排序。

Answer 3

这里有很多错误。

首先，您的方法：

private static void insertionSort(ArrayList<Integer> arr) {
   insertionSort();
}

获取一个 ArrayList 并完全忽略它。这大概应该是需要排序的List。

然后在insertionSort()创建一个新的 ArrayList，按顺序插入一些数字，然后尝试一些看起来不像插入排序，但更像气泡排序的东西。

因此，当您调用insertionSort(List)时，它实际上根本不会对列表执行任何操作，insertionSort()中的所有工作都发生在完全不同的List上！

由于在SO上我们通常不会为他们做功课，我建议查看此页面上漂亮的小动画图表

那么你应该拥有的是这样的：

public void insertionSort(LinkedList<Integer> numbers) {
   //do stuff with numbers, using get() and add()
}