快速排序算法scratch柱形图模拟演示之说明
本视频内容包括:
快速排序算法 scratch柱形图演示说明
问题与解决: 快速排序演示中的“暂停效果”的实现
总结：解决问题的方法(之一)
一、快速排序算法 scratch柱状图演示说明 (本项目的输出的应用场合：讲解快速排序时)
1.操作说明： |
1.点绿旗 按A键 ―――绘柱形图 2.按 右箭头 键 ――――quick sort 3.可按 空格 暂停 |
|
2.舞台上的变量指示： |
指针j 指针i 基准值key 演示中的“暂停状态”指示 |
|
3.柱形图： |
柱形图：高度（颜色）表示数值大小 Dorees始终在表示 key 的柱形上 柱形下的j、 i: 表示j、 i指针 |
|
4.链表 |
排序的数值：quicksort时数字会跳动 |
|
以上是 停止状态的舞台 |
||
5.演示说明 |
a |
按上述操作说明1.2.之后，柱形图出现在舞台上，但并未排序。 此时，暂停状态为1（开始将这个变量设定为1而不是0） 这时：dorees方向向右，表示接下来是指针j会移动
注意：这里“故意”按变量pause=1,使 按上述操作说明12之后 并不开始排序，这样做只是为了演示用。 |
b |
按空格, 暂停状态为0: quickSort |
|
c |
Quick Sort过程中如按 空格键：暂停状态变为1 可观察 dorees方向 链表数值 猜测是哪个指针向哪个方向移动且到何时停止移动…… 以此来了解 快速排序指针法 的做法。 |
|
d |
再按空格, 暂停状态为0; 重新quick Sort 验证你在c步的猜测 |
|
… |
||
二、问题与解决
问题： |
|
1 |
希望快速排序时，先显示柱形图下的指针j和i再开始排序 |
2 |
暂停效果如何达成，想在快速排序过程中将排序过程暂停 |
2.1 |
暂停后重启quick sort时，想知道重启后是哪个指针开始移动：想用dorees的方向作为“提示”，如何达成 |
3 |
3.1点绿旗 按A键 ―――绘柱形图 3.2按 右箭头 键 ――――quick sort 操作说明中按A绘 柱形图 按右箭头quicksort
但是，在quicksort过程中或暂停时，再按A或右箭头：程序还是会有上面的动作----这是我们不希望的，如何改进？ |
…… |
|
问题解决：
增加 暂停功能：完美解决 2.增加变量pause在按下空格时将之设定为1：在quicksort中增加 如果pause=0 那么…移动指针 2.1增加变量dj di分别表示指针j、指针i的状态：是否移动----0或1 这样，dj+di=0时是j=I;而di-dj=1或-1刚好表示是j还是i的移动方向（90或-90） [见本文后 附录]
3. 增加变量kg: 在quicksort 中为1；同时利用n=0不成立：解决 |
|
问题解决总结：充分利用 变量。
如何找到解决问题的办法：从流程（线程）找差异，利用差异
快速排序代码实现与 柱状图演示 项目总结
①快速排序 指针交换法 好过 “填坑法”。
②递归如何“跳出”，递归结束条件？
③还充分利用“变量”；充分利用自定义积木――用好这两个你才是有可能算是学好了scratch。
④如何找到解决问题的办法（之一）：从流程（线程）找差异，利用差异
附录
演示中暂停 功能的添加
增加一个按空格键 暂停的功能
按空格键时 将变量pause=1
此时j 、i的增加均停止（将pause=0 放在j或i增加代码中）
其它动作也相应停止
难点是：如何确定dorees的方向―――以dorees方向来表示是j还是i在移动（移动方向的指示），以dorees的方向作为下一步的指针j或i移动的方向。
下图1表示开始时，j指针开始向左移动。下图2表示下一刻指针i将向右移动。
图1
图2
增加变量dj di：分别表示指针j i的状态（是否移动）――为0（不移动）或1（移动）：（快速排序程序运行时：时序为：dj=1 dj=0 di=1 di=0 然后重复以上时序；）
Quicksort中dj di的值的变化：
NO |
指针移动状态 |
dj |
di |
dj+di |
di-dj |
a |
j指针移动 |
1 |
0 |
1 |
-1 |
b |
j指针停止 |
0 |
0 |
0 |
0 |
c |
i指针移动 |
0 |
1 |
1 |
1 |
d |
i指针停止 |
0 |
0 |
0 |
0 |
dj+di值在1、0之间转换，di-dj值为-1,0,1:对应方向-90度，180度，90度。
这样，dj+di=0时是j=I;而di-dj=1或-1刚好表示是指针j或指针i的方向（90或-90）
所以dorees的方向代码如下：
视频教程：