public static void insertionSort(int[] a) {
  if (a == null || a.length < 2)
    return;
  int j;
  for (int i = 1, temp = a[i]; i < a.length; i++) {
    for (j = i - 1; j >= 0 && temp < a[j]; a[j + 1] = a[j], j--);
    a[j + 1] = temp;
  }
}


期望以升序对int数组进行排序。但是对于输入数组{ 1, 2 ,3 , 7 , 8 , 6 , 100 , 99 , 98},它给出输出[1, 2, 2, 2, 2, 2, 2, 2, 2]

为什么此插入排序代码无法按预期工作?

最佳答案

通过将temp = a[i]放在外部循环的初始化子句中,可以确保它仅运行一次。在您给出的示例中,temp将被分配为2,并且您绝不会将其更改为其他任何内容。

然后,在循环的其余部分中,只要有更大的条目,就最终将temp的值分配给数组中的其他条目。因此,大多数数组最终都被设置为2。

因此,temp = a[i]必须位于外部循环的主体中,而不是位于其初始化子句中。

09-30 15:50
查看更多