在for循环里使用数据更新错误
来源：2-3 插入排序法的一个小优化
weixin_慕容5064376
2023-01-20 15:06:04
public static <T extends Comparable<T>> void Sort2( T[] data ) {
// 从第二个数据开始，需要进行插入排序
for( int i = 1 ; i < data.length; i++ ){
// 向前进行插入操作, 循环不变量[0, i)
T elem = data[i]; //要比较的元素
int j;
for( j = i - 1; j >= 0; j-- ) {
if ( elem.compareTo( data[j] ) > 0 ){
data[j] = elem; //错误
break;
}
// 元素后移
data[ j + 1 ] = data[j];
}
}
}bobo老师，
对于这个优化，我如果在第二层for循环里使用data[j] = elem;后再break;就会得到错误的结果；而且排序后数组依然可以保持有序，骗过了isSorted。如果移到for循环之外就好了。既然break可以跳出循环起到同样的作用，为什么在内外效果不同呢。逻辑上我看不出错误。麻烦您指导！
写回答
1回答
-
liuyubobobo
2023-01-20
因为元素 elem 可能比他之前的所有元素都要小，也就是 if(elem.compareTo(data[j]) > 0) 一直是 false。在这种情况下，你的这个代码的 if 永远不会执行。（但课程的代码在这种情况下也没有问题，想想是为什么？）
可以使用单步跟踪的方式看一下，对于你的代码，排序 [2, 1] 就会得到错误的结果。用这个极小的错误用例仔细看一下，你的程序是如何执行的？为什么会得到错误的结果？哪一步和自己的思考不一致了？自己哪里想错了？这是非常重要的学习算法，甚至是学习计算机所有领域的方式哦。
继续加油！：）
0h023-01-21
相似问题
第二层for循环出现问题
回答 1
循环不变量定义
回答 3