为什么我的插入排序没有通过这个测试用例？

Question

我正在尝试编写插入排序，我通过了几个测试用例，但有一个未通过。我的代码是：

static void insertionSort1(int n, int[] arr) {


    int copy = arr[n-1];

    int i = n - 1;
    while (copy < arr[i-1]){

        arr[i] = arr[i-1];

        for(int k = 0; k < arr.length; k++){
            System.out.print(arr[k] + " ");
        }
            System.out.println();
        i--;
        }
     arr[i] = copy;
    for(int m = 0; m < arr.length; m++){
       System.out.print(arr[m] + " ");
     }
    }

其中n是数组的大小，arr是数组。我的算法尤其未能通过此测试用例：

10

2 3 4 5 6 7 8 9 10 1

我得到的索引超出范围，但

5

2 4 6 8 3

或其他人。怎么回事？

Answer 1

首先，您应该回顾一下什么是插入排序。您应该在数组的一端构建一个排序列表，通过 "inserting" 正确位置的下一个值一次扩展一个元素。如果一次给一张牌，这应该很像对一手牌进行分类。您将需要一个嵌套循环才能正确执行此操作。

仔细考虑你的程序真正在做什么，看看它失败的原因——以同样的方式失败的更短的测试用例将是 [3, 2, 1]。或者 [2, 1]，就此而言。

Answer 2

这是数组的索引越界异常，因为arr的负值。这不是算法问题，而是语言问题。

while (i > 0 && copy < arr[i - 1])

来源：

public class InsertionSort {
    static void insertionSort1(int n, int[] arr) {

        int copy = arr[n - 1];

        int i = n - 1;
        while (i > 0 && copy < arr[i - 1]) {

            arr[i] = arr[i - 1];

            for (int k = 0; k < arr.length; k++) {
                System.out.print(arr[k] + " ");
            }
            System.out.println();
            i--;
        }
        arr[i] = copy;
        System.out.println("#### RESULT ####");
        for (int m = 0; m < arr.length; m++) {
            System.out.print(arr[m] + " ");
        }
        System.out.println("\n#### END ####\n");
    }

    public static void main(String[] args)
    {
        //10
        //2 3 4 5 6 7 8 9 10 1
        int[] arr ={2, 3, 4, 5, 6, 7, 8, 9, 10, 1};
        int n = arr.length;
        insertionSort1(n, arr);


        //5
        //2 4 6 8 3
        arr= new int[5];
        n = arr.length;

        arr[0] = 2;
        arr[1] = 4;
        arr[2] = 6;
        arr[3] = 8;
        arr[4] = 3;

        insertionSort1(n, arr);
    }
}

结果：

2 3 4 5 6 7 8 9 10 10 
2 3 4 5 6 7 8 9 9 10 
2 3 4 5 6 7 8 8 9 10 
2 3 4 5 6 7 7 8 9 10 
2 3 4 5 6 6 7 8 9 10 
2 3 4 5 5 6 7 8 9 10 
2 3 4 4 5 6 7 8 9 10 
2 3 3 4 5 6 7 8 9 10 
2 2 3 4 5 6 7 8 9 10 
#### RESULT ####
1 2 3 4 5 6 7 8 9 10 
#### END ####

2 4 6 8 8 
2 4 6 6 8 
2 4 4 6 8 
#### RESULT ####
2 3 4 6 8 
#### END ####

祝你有美好的一天。

为什么我的插入排序没有通过这个测试用例？

Why is my insertion sort failing this test case?

java

sorting

insertion-sort

indexoutofboundsexception