如何对合并排序可视化进行动画处理/绘制?

Question

我想为我的排序可视化工具设置合并排序算法的动画，但问题是与其他一些算法不同，合并排序是递归的，因此您可以通过传递原始数组的一段来不断从函数内部调用函数。当我尝试绘制它时出现问题，因为我无法绘制较小的数组，但我必须不断更新原始数组。我对该怎么做感到困惑，因为要绘制过程，我需要对原始数组有效的特定值的索引，而不是较小的值。有人有想法或解决方案吗？

Answer 1

您可以通过编写将原始数组和索引值传递给要排序的切片的合并排序来实现目标。

下面是 javascript 中的一个例子：

function merge(a, lo, m, hi) {
var tmp = [];
var len = m - lo;
var i, j, k;
// save left subarray
for (i = 0; i < len; i++) {
// animate this move
tmp[i] = a[lo + i];
}
// merge subarrays
i = 0;
j = m;
k = lo;
while (i < len && j < hi) {
if (tmp[i] <= a[j]) {
// animate this move
a[k++] = tmp[i++];
} else {
// animate this move
a[k++] = a[j++];
}
}
// copy the remaining elements
while (i < len) {
// animate this move
a[k++] = tmp[i++];
}
}
function mergesort(a, lo, hi) {
if (hi - lo > 1) {
var m = lo + ((hi - lo) >> 1);
mergesort(a, lo, m);
mergesort(a, m, hi);
merge(a, lo, m, hi);
}
}