java - 为什么使用 arraylist 实现的插入排序没有输出也没有错误？

Question

我希望任何人都可以帮助我编写以下 Java 代码，因为即使它没有显示任何错误，它也没有给出数组作为输出: 我正在尝试实现插入排序。我制作了 2 个包和类；一个主要的和一个 InsertionSort 的。 我使用的代码是:

package main;

import java.util.ArrayList;
import insertionSort.InsertionSort;

public class Main implements Cloneable{

    public static void main(String[] args){

        ArrayList<Integer> unsortedArray = new ArrayList<Integer>();
        unsortedArray.add(8);
        unsortedArray.add(7);
        unsortedArray.add(6);
        unsortedArray.add(5);
        unsortedArray.add(4);
        unsortedArray.add(0);
        unsortedArray.add(2);
        InsertionSort sort = new InsertionSort(unsortedArray);

        System.out.println("Initial unsorted array: ");
        for(int i:InsertionSort.inputArray()){
            System.out.print(i + " ");
        }

        sort.doInsertionSort();

        System.out.println("Sorted array after performing insertion sort: ");
        for(int i:InsertionSort.inputArray()){
            System.out.print(i + " ");
        }

    }
}


package insertionSort;

import java.util.ArrayList;

public class InsertionSort {

private static ArrayList<Integer> array = new ArrayList<Integer>();
public static ArrayList<Integer> inputArray() {
        return array;
    }   

    public InsertionSort(ArrayList<Integer> inputArray){
        InsertionSort.array = array;
    }

    public void doInsertionSort(){
        for (int j = 1; j<array.size(); j++){
            int key = array.get(j);
            int i;
            for (i=j-1; i>=0 && array.get(i)> key; i--){
                array.set(i+1,array.get(i));
                array.set(i+1, key);
            }
        }
    }
}

我得到的输出只是没有数组的文本。希望有人能帮忙!请记住我是新手。提前谢谢你:)

Answer 1

这会将 array 变量分配给它自己:

public InsertionSort(ArrayList<Integer> inputArray){
    InsertionSort.array = array;
}

这应该是:

public InsertionSort(ArrayList<Integer> inputArray){
    array = inputArray;
}

此外，你的交换有一点错误。

array.set(i+1, key);应该在内层循环之后执行。
它将外循环的元素(由 key 变量引用)设置在正确的位置。
仅当您对其左侧的元素进行排序时才必须这样做，因此在内循环之后。

所以这个:

for (i=j-1; i>=0 && array.get(i)> key; i--){
    array.set(i+1,array.get(i));
    array.set(i+1, key);
}

应该是:

for (i=j-1; i>=0 && array.get(i)> key; i--){
    array.set(i+1,array.get(i));
}
array.set(i+1, key);

---

附带说明一下，您没有正确使用实例和静态修饰符。

您创建一个 InsertionSort 的实例:

InsertionSort sort = new InsertionSort(unsortedArray);

但是构造函数值一个静态字段。

...
private static ArrayList<Integer> array = new ArrayList<Integer>();

public InsertionSort(ArrayList<Integer> inputArray){
    InsertionSort.array = array;
}

为什么在这种情况下创建一个实例？

InsertionSort 有一个特定于您传递给的 List 的状态，因此您不应该对其成员使用 static 修饰符应该关联到InsertionSort 的一个 实例。 所以用实例修饰符替换静态修饰符。