代码之家 › 专栏 › 技术社区 › Flame_Phoenix

使气泡排序纯净高效

bubble-sort algorithm javascript

-2

Flame_Phoenix · 技术社区 · 8 年前

出身背景

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

目标

函数必须是纯函数
它必须是高效的
它必须遵守中列出的复杂性 https://en.wikipedia.org/wiki/Bubble_sort

请注意,“纯净”并不意味着它的内部代码不能有杂质。这仅仅意味着函数的公共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的任何缺陷。

我也在寻找提高其效率的方法,因为我确信垃圾收集器是否那么喜欢递归性(大多数浏览器还没有实现尾部调用优化…)。

1 回复 | 直到 8 年前

Bergi 8 年前

关于目标1,您的代码在保持纯净方面做得很好——它只是克隆了所有内容。

然而,这与目标3并不相符。而 recursiveSort 是预期的吗 O(nÂ²) ,克隆数组的整个内容会增加复杂性负担,现在复杂性不仅取决于输入数组的长度,还取决于元素的大小和深度。由于排序无论如何都不会对元素进行变异,这是没有意义的-您可以而且应该只返回一个包含原始对象的新数组。纯净的一个主要目标是允许分享!

所以使用

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 .