让冒泡排序变得纯​​粹和高效

Question

背景

我正在与一位同事一起重新编写一系列算法，稍后我们将在一个数据包中为社区发布这些算法。

首先，我选择了典型的冒泡排序算法。

目标

1. 函数必须是纯的
2. 一定要有效率
3. 它必须遵守 https://en.wikipedia.org/wiki/Bubble_sort
中列出的复杂性

请注意，"being pure"并不意味着它的内部代码不能有杂质。它只是意味着函数的 PUBLIC API 必须是纯粹的，并且它不能影响其范围之外的任何东西。

代码

const isFunction = require("lodash.isfunction");
const cloneDeep = require("lodash.clonedeep");

const defaultCompare = require("./defaultCompare");

const bubble = ( array, fnCompare = defaultCompare ) => {

    if( !isFunction(fnCompare) )
        throw new Error("fnCompare must be a function");

    if(!Array.isArray(array))
        throw new Error("array must be an Array");

    if (array.length === 0)
        return [];

    const clonedArray = cloneDeep(array);

    return recursiveSort( clonedArray, clonedArray.length, fnCompare );
};

const recursiveSort = ( array, unsortedLength, fnCompare ) => {
    if( unsortedLength === 1 )
        return array;

    let swapped = false;
    for( let i = 0; i < unsortedLength - 1; i++ ){

        if( fnCompare( array[i], array[i + 1] ) > 0 ){
            const temp = array[i];
            array[i] = array[i + 1];
            array[i + 1] = temp;
            swapped = true;
        }
    }

    //Ensure O(n) if array is already ordered
    if(!swapped)
        return array;

    return recursiveSort( array, unsortedLength - 1, fnCompare );
};

module.exports = bubble;

我想要什么？

我正在寻找代码中可能危及目标 1 和 3 的任何缺陷。

我也在寻找提高效率的方法，因为我确定垃圾收集器是否非常喜欢递归（尾调用优化尚未在大多数浏览器中实现......）。

Answer 1

关于 objective 1，您的代码在纯净方面做得很好 - 它只是克隆所有内容。

虽然这与 objective 3 不相符。虽然 recursiveSort 的复杂度是预期的 O(n²)，但克隆数组的全部内容会给复杂度带来额外的负担，现在它不仅取决于输入数组的长度，还取决于大小和元素的深度。因为无论如何排序都不会改变元素，所以这是没有意义的——你可以而且应该 return 一个包含原始对象的新数组。纯度的主要目标是允许共享！

所以使用

function bubbleSorted(array, fnCompare = defaultCompare) {
    if (typeof fnCompare != "function")
        throw new Error("fnCompare must be a function");
    if (!Array.isArray(array))
        throw new Error("array must be an Array");

    return recursiveSort(array.slice(), array.length, fnCompare);
}

另请注意，您有许多不必要的基本案例。您的算法只需要在 swapped 为假时停止。您不需要对 0 或 1.

的数组长度进行额外测试