如何对合并排序可视化进行动画绘制？

Question

我想给我的排序可视化器的合并排序算法做动画，但问题是，与其他一些算法不同，合并排序是递归的，所以你要通过传递一段原始数组，从函数内部不断调用函数。当我尝试绘制的时候，问题就出现了，因为我无法绘制较小的数组，但我必须不断地更新原始数组。我很困惑该怎么办，因为要绘制过程，我需要对原始数组有效的特定值的索引，而不是较小的数组。有谁有办法或解决方法吗？

Answer 1

你可以通过编写mergesort将原始数组和索引值传递给被排序的片子来实现你的目标。

下面是一个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);
    }
}