ArrayLinkedList插入排序

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。它们之间有很大的不同。

第二，也许更切中要害。在内部循环中，您保存了一个temp变量，并交换了位置k-2和k-1处的元素。从评论来看，这不是你老师的本意。由于他希望您解决元素插入的问题，因此我建议您查看LinkedList.add(int，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上！

既然这样，我们通常不会为人们做作业，我建议看看this page上漂亮的小动画diagram

然后，您应该拥有类似以下内容：

public void insertionSort(LinkedList<Integer> numbers) {

   //do stuff with numbers, using get() and add()
}