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]
必须位于外部循环的主体中,而不是位于其初始化子句中。