关于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

同学,你好:


在使用编辑器时可以使用“插入代码”功能,可保证讲师更快的理解你的问题并解答。

操作方法如下:

https://img1.sycdn.imooc.com/climg/6596512108467edb05771012.jpg

0

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 的,满足循环不变量
}


继续加油!:)

0

算法与数据结构

波波老师5年集大成之作,算法与数据结构系统学习,考试、面试、竞赛通用

2584 学习 · 1063 问题

查看课程