算法的两种心智模型：代数与几何

Question

人类发展了两类反映世界的心智模型：语言和代数 vs 视觉和几何。分别对应「语义化」和「可视化」。

几乎所有人都具备使用和表达它们的能力。但不同的人对它们的依仗程度不同，甚至同一个人面对不同的问题时所采用的心智模型也可能不同。

下面的 merge sort 小测验，考量你对算法问题的处理方式是「代数型」、「几何型」还是「综合型」。

鉴定方式是，在看完对 merge sort 的两种类型的解读之后，自行体悟，报告出当你从头实现 merge sort 时，你倾向于用哪一种心智模型作为想象图景。

静态几何型

动态几何型

merge sort visualizer 点击链接，等待加载完成后，点击右上角导航条里的 run 按钮观看。

递归代数型

/**
 * 先写合并两个已排序的数组的函数
 */
function merge(left, right) {
    var result = []
    while (left.length > 0 || right.length > 0) {
        // left, right 数组任意一个长度为 0 时，拼接另一个数组即可（已排序） 
        if (left.length === 0) {
            return result.concat(right)
        } else if (right.length === 0) {
            return result.concat(left)
        }
        // 按从小到大排序，如果两数相等，一起 push 进去
        if (left[0] < right[0]) {
            result.push(left.shift())
        } else if (left[0] > right[0]) {
            result.push(right.shift())
        } else {
            result.push(left.shift(), right.shift())
        }
    }
    return result
}

/**
 * 对于未排序的数组，不断分解数组
 * 分出两个长度为 1 的数组后，它们就成了已排序的数组，调用 merge 函数
 * 递归地调用 mergeSort 把「已排序的小数组」合并成「已排序的大数组」
 */
function mergeSort(list) {
    if (list.length === 0 || list.length === 1) {
        return list.slice(0)
    }
    var halfLength = Math.floor(list.length / 2)
    var head =  list.slice(0, halfLength)
    var tail = list.slice(halfLength)
    var left = mergeSort(head)
    var right = mergeSort(tail)
    return merge(left, right)
}

mergeSort([38,27,43,3,9,82,10,123,5,23,5,7,23,4,7,25,23,42,
362,34,234,2,342,34,234,2,36,7,8,3,4,234,12,4,234,2,35,235,1])

队列代数型

/**
 * 先写合并两个已排序的数组的函数
 */
function merge(left, right) {
    var result = []
    while (left.length > 0 || right.length > 0) {
        // left, right 数组任意一个长度为 0 时，拼接另一个数组即可（已排序） 
        if (left.length === 0) {
            return result.concat(right)
        } else if (right.length === 0) {
            return result.concat(left)
        }
        // 按从小到大排序，如果两数相等，一起 push 进去
        if (left[0] < right[0]) {
            result.push(left.shift())
        } else if (left[0] > right[0]) {
            result.push(right.shift())
        } else {
            result.push(left.shift(), right.shift())
        }
    }
    return result
}

function mergeSort(list) {
    if (list.length === 0) {
        return []
    } else if (list.length === 1) {
        return [list[0]]
    }

    // 复制一份 list，并把元素数组化，使之成为长度为 1 的「已排序数组」
    var queue = []
    for (var i = 0; i < list.length; i++) {
        queue[i] = [list[i]]
    }

    // 以队列形式，从头至尾，不断两两合并「已排序的数组」，直到队列里只剩一个「已排序数组」
    while (queue.length > 0) {
        if (queue.length === 1) {
            return queue[0]
        }
        var left = queue.shift()
        var right = queue.shift()
        // 把新的「已排序数组」放到队列的末尾
        queue.push(merge(left, right))
    }

    return queue[0]
}

mergeSort([38,27,43,3,9,82,10,123,5,23,5,7,23,4,7,25,23,42,362,
34,234,2,342,34,234,2,36,7,8,3,4,234,12,4,234,2,35,235,1])

所以，你是什么类型呢？