关于2-3小节的循环不变量
来源:2-3 插入排序法的一个小优化
黑白琴键3675322
2023-12-02 15:09:19
在【2-3.插入排序法的一个小优化】中,复制或移动数据的这个循环中,是否可以用循环变量和循环不变量来指导我们写出正确的数据移动算法?如果可以的话,在这其中的循环变量和循环不变量分别是什么?
target = data[i]j(j = ij > && data[j -].compareTo(target) > j --) { data[j] = data[j - ]} data[j] = target
2回答
Fr_View
2024-01-04
同学,你好:
在使用编辑器时可以使用“插入代码”功能,可保证讲师更快的理解你的问题并解答。
操作方法如下:
liuyubobobo
2023-12-03
你给的代码格式乱掉了,我估计是慕课网的问题,我已经把这个问题反馈给了慕课网。
我猜说的是课程代码这里的 30-32 行:https://git.imooc.com/class-105/Play-Algorithms-and-Data-Structures/src/master/04-Insertion-Sort/03-Insertion-Sort-Optimized/src/InsertionSort.java
循环不变量如下:
// 每次循环开始的时候,arr[j...i] 范围的元素都是有序且 >= t 的。(循环不变量) for(j = i; j - 1 >= 0 && t.compareTo(arr[j - 1]) < 0; j --){ arr[j] = arr[j - 1]; // 如果 arr[j - 1] >= t (或者 t < arr[j - 1]) // 则执行 arr[j] = arr[j - 1] // 之后 j -- // 则新的 arr[j..i] 范围内的元素,依旧是有序且 >= t 的,满足循环不变量 }
继续加油!:)
相似问题