Java 插入排序

Question

下面是我在学习AP Computer Science时遇到的Java中进行插入排序的方法：

public static void insertionSort(int[] x)
{
    for (int i=1;i<x.length;i++)
    {
        int temp = x[i];
        int j=i-1;
        while (temp<x[j]&&j>=0)
        {
            x[j+1]=x[j];
            j--;
        }
        x[j+1]=temp;
    }
}

逻辑上，我认为代码是正确的。但是，当我尝试使用以下代码使用该方法对列表进行排序时：

public static void main(String[] args)
{
    int[] numList ={9,3,12,765,23};
    insertionSort(numList);
    for (int num:numList)
    {
     System.out.println(num);
    }
}

我得到以下异常：线程“main”中的异常java.lang.ArrayIndexOutOfBoundsException：索引 -1 超出长度 5 的范围

这里有什么问题？

Answer 1

使用while (j>=0&&temp<x[j]) 不是 while (temp<x[j]&&j>=0)

Answer 2

您遇到了评估顺序问题。您的条件（temp < x[j] 和 j >= 0）是正确的，但由于您编写它们的顺序，x[j] 在与 0 比较之前被评估为与 temp 进行比较。将您的条件反转为 j >= 0 && temp < x[j] 即可解决。

感谢短路评估 (https://en.wikipedia.org/wiki/Short-circuit_evaluation)，由于 j >= 0 为假，x[j] 将不会被评估。

Answer 3

在 insertionSort 方法的 while 循环中你的语句应该是这样的

while (j >= 0 && x[j] > temp)

Java 插入排序

Java Insertion Sorting

java

sorting

insertion