排序算法怎么单步看懂:演示台伪代码与变量对照
TL;DR
用单步演示看懂排序,关键不是背代码,而是每按一次“下一步”只核对三处:伪代码高亮行、数组或柱子状态、变量表。输入只在浏览器里计算,不上传;页面没有账号和登录。先改输入,再逐步前进或后退,比较次数和交换次数会跟着当前步骤更新。高亮行表示正在执行的那一行,不是执行结果。
先看结论:单步演示盯住三栏
单步演示的价值在对应关系。伪代码告诉你现在执行哪条规则,数组或柱子显示数据怎么动,变量表给出当前步骤的变量和计数。读一帧时,先看高亮行,再看数据变化,最后用变量表确认边界和计数。这样比只看动画结果更容易发现循环边界、交换条件和提前退出的作用。 变量表会随算法显示不同字段。排序演示里常见i、j、比较次数和交换次数;顺序查找看i;二分查找看low、high、mid。
演示台能演示什么,输入怎么填
排序有冒泡、插入、选择、归并、快速、堆排序六种;查找有顺序查找和二分查找。每个算法有单独一页,包含演示、复杂度、要点和常见错误。 输入框接受负数,可以构造含负数的数组。顺序查找不要求数组有序;二分查找的闭区间写法针对升序数组。 改完数字后点“生成演示”。想看最坏情况,就专门构造一个最坏输入。
操作盘:前进、后退、播放和速度各管什么
页面提供上一步、下一步、播放/暂停和慢、中、快三档速度。键盘←→单步,空格播放/暂停,先点一下演示区。 读循环时用“下一步”逐帧走。想回看上一帧,用“上一步”。变量表跟着当前步骤更新。自动播放适合先看整体节奏,慢速适合对照伪代码;关键步骤直接暂停。洋红色标出此刻正在比较或移动的元素。
三栏联动:高亮行、图形和变量表怎么对
每按一次“下一步”,右侧伪代码亮起正在执行的那一行,变量表同步更新。伪代码用←表示赋值。高亮到比较行时,看洋红色元素和j的值;高亮到交换行时,看数组位置和交换次数是否增加。 变量表的具体字段随算法不同。排序演示通常要盯i、j、比较次数、交换次数;查找演示要盯i或low、high、mid。 不要把高亮行当成“已经执行完”的行。页面说的是亮起正在执行的那一行。看到高亮行时,先判断这一步的动作,再按下一步看结果。
冒泡排序逐帧:比较、判断、交换
冒泡排序重复遍历列表,比较相邻元素;前一个比后一个大就交换。每轮结束,当前最大值会被送到未排序区末尾,下一轮缩小范围。 单步时把一轮拆成三拍:比较相邻两个数,判断是否逆序,需要时交换。变量表里的比较次数和交换次数会随步骤变化。一轮结束时先别急着前进,记下这一轮的交换次数;下一轮开始前再看它有没有变化。 提前退出优化用一个标记记录本轮是否发生交换;没有交换就说明列表已经有序,可以结束。演示台的变量表提供比较次数和交换次数;结合提前退出规则,可以在每轮结束时看交换次数有没有增加。
换成选择排序:看已排序区边界
选择排序每轮从右侧未排序序列里选最小元素,再和未排序序列的第一个元素交换。单步时重点看未排序区起点怎么移动,以及交换发生在哪个位置。 冒泡排序的交换发生在相邻元素之间;选择排序一轮通常只交换一次,把选中的最小元素放到未排序区开头。两种算法的交换次数差别,在变量表的交换计数上会直接反映出来。 插入排序页也可以按三栏联动读;具体变量名以该算法页的变量表为准。
查找演示:顺序查找和二分查找看什么
顺序查找从第一个数开始逐个比较,遇到目标就返回位置;全部看完没有就返回−1;不要求数组有序。目标在第一个位置时只比较1次;不在数组里时要比较n次。有重复值时返回第一次出现的位置。 二分查找用闭区间[low, high],初始为[0, a.length−1];mid取low和high的均值;midVal小于key时low=mid+1,大于key时high=mid−1,循环条件是low≤high。单步时每走一步都检查:如果key在数组里,它是否仍在当前[low, high]内。这就是区间不变量。
常见误读:高亮行、循环边界和速度
高亮行是正在执行的行,不是执行完的结果。看到高亮行时,先读这一行动作,再按下一步看数据变化。 循环边界要看变量表,不要只看柱子移动。冒泡排序每轮缩小范围;二分查找的low和high必须配套更新。 动画速度不是算法复杂度。 演示台只演示通用算法怎样一步步执行,不代写作业和代码,不代做题目,也不提供考试答案。
读者问答
伪代码高亮行表示“即将执行”还是“刚执行完”?
页面说明右侧伪代码会亮起正在执行的那一行。读的时候把高亮行当作当前动作,不是已经得到的结果。
前进和后退时,变量表会跟着回滚吗?
页面提供上一步和下一步,变量表随当前步骤同步更新。逐帧核对时,以当前步号和变量表为准。
演示要注册或联网吗?机房离线能不能用?
输入只在浏览器里计算,不会上传;页面没有账号和登录。关掉页面,输入的数据就没有了。
二分查找的区间不变量怎么用单步验证?
闭区间写法初始为[0, a.length−1];midVal小于key时low=mid+1,大于key时high=mid−1,循环条件是low≤high。每一步检查key若存在,是否仍在[low, high]内。
冒泡排序的提前退出在单步里看什么?
提前退出靠“本轮是否发生交换”判断:没有交换说明已经有序。演示台变量表提供比较次数和交换次数;可以在每轮结束时看交换次数有没有增加。
能把过程导出成笔记吗?
现有页面说明未提到导出、截图或步骤记录;页面显示当前步号。做笔记时可记录输入、步号和变量表数值。