什么时候以及为什么有些项目甚至没有在排序算法中进行比较？

Question

我有一个案例，我需要按多标准对字符串数组进行排序。想象一下，我们正在复制目录路径列表。鉴于以下要求，我需要排序来产生 always 相同的结果。输入的初始顺序无关紧要。

每个项目都是一个路径字符串，可能在任何地方包含一个 glob/wildcard 星号 *。
例如*/foo 或 foo/* 或 foo/*/bar.. 你明白了。
每个项目可能还包含一个前缀 !，它否定值。
例如!bar/norf 表示删除此路径。

要求：

如果比较的两条路径相等，其中一条取反（!）；被否定的应该排在最后。例如bar/norf 在 !bar/norf
级别数较少的路径应排在第一位。
例如foo/bar 在 foo/baz/*
松散 paths/globs 应该放在第一位，verbose/exact 路径应该放在最后。
例如foo/* 在 foo/bar/* 之前在 foo/bar/baz.

尝试次数：

现在，如果我使用快速排序或合并排序等算法，大多数时候我会得到预期的结果，但当我更改初始顺序或项目数量时，它会失败。特别是对于上面的第一个要求。贝克。有时（取决于初始订单或商品数量）有些商品不会直接相互比较。

var unsorted_CASE1 = [ 
    'foo/bar/baz', 
    '!bar/norf', 
    'bar/x', 
    'bar/norf', 
    '!foo/*/baz', 
    '!bar/*', 
    'foo/qux/*' 
];
console.log( mergeSort(unsorted_CASE1, compareFn) );
// expected correct output
[ 
    '!bar/*',      // 0
    'bar/norf',    // 1
    '!bar/norf',   // 2
    'bar/x',       // 3
    '!foo/*/baz',  // 4
    'foo/qux/*',   // 5
    'foo/bar/baz'  // 6
]

var unsorted_CASE2 = [
    'foo/bar/baz',
    '!bar/norf',
    'bar/x',
    'bar/norf',
    '!foo/*/baz',
    '!bar/*',
    '!foo/qux/boo', // added a new item here, no other change
    'foo/qux/*'
];
console.log( mergeSort(unsorted_CASE2, compareFn) );
// incorrect output
[ 
    '!bar/*',      // 0
    '!bar/norf',   // 1 (should have come after bar/norf (3))
    'bar/x',       // 2
    'bar/norf',    // 3
    '!foo/*/baz',  // 4
    'foo/qux/*',   // 5
    'foo/bar/baz', // 6
    '!foo/qux/boo' // 7
]

这里 '!bar/norf' 和 'bar/norf' 从来没有直接相互比较过。结果，被否定的在前，预计在后。

编辑 1: 我不是要实现排序算法。我当然为此使用外部库。我试图了解某些项目何时以及为何未进行比较并产生此结果。并且此处使用的排序算法是否需要所有可能的排列以获得预期结果。如果不是，哪种著名算法最适合这里？还是不是排序算法？就这些了。

编辑 2： 这是比较函数：

function compareFn(oA, oB) {
    var aNeg = oA.slice(0, 1) === '!',
        bNeg = oB.slice(0, 1) === '!',
        a = aNeg ? oA.slice(1) : oA,
        b = bNeg ? oB.slice(1) : oB;
    // "foo/bar" vs "!foo/bar" » equal » negated wins (comes last)
    if (a === b) {
        return aNeg ? 1 : -1;
    }
    // if not equal » e.g. "!*/foo/*" vs "*/foo/bar"
    // "*/foo/bar" comes last
    var A = a.split('/'),
        B = b.split('/'),
        numLevelsA = A.length,
        numLevelsB = B.length;
    // glob having the less number of levels comes first
    // e.g. "bar/*" comes before "bar/baz/*"
    if (numLevelsA < numLevelsB || a === '*') { return -1; } // a first
    if (numLevelsA > numLevelsB || b === '*') { return 1; } // b first
    // number of levels are equal:
    var lA, lB, i = -1;
    while (++i < numLevelsA) {
        lA = A[i];
        lB = B[i];
        // levels are not equal
        if (lA !== lB) {
            // "*" comes before "a*bc"
            // level IS star "*"
            if (lA === '*' && lB !== '*') { return -1; }
            if (lA !== '*' && lB === '*') { return 1; }
            // level has star "a*bc"
            if (lA.indexOf('*') >= 0 && lB.indexOf('*') < 0) { return -1; }
            if (lA.indexOf('*') < 0 && lB.indexOf('*') >= 0) { return 1; }
        }
        // else if levels are equal,
        // continue to next level
    }
    // no order
    return 0;
};

注意：这是一个非常简化的问题版本。我没有实施 minimatch 或类似的库。（事实上，项目甚至不是路径字符串）。所以请不要建议已经这样做的库。我正在尝试 establish/understand 逻辑。

Answer 1

我从头开始重写了比较函数，我认为这个有效：

function compare(a, b) {
    // trivial case, both are exactly the same!
    if (a === b) {
        return 0;
    }
    var levelsA = a.split("/");
    var levelsB = b.split("/");

    // Check depth (number of levels)
    if (levelsA.length === levelsB.length) {
        // count wildcards (assuming more wildcards comes first)
        var wild = /(?:^|\/)\*(?:$|\/)/g;
        var mA = a.match(wild);
        var mB = b.match(wild);
        var wildA = mA ? mA.length : 0;
        var wildB = mB ? mB.length : 0;
        if (wildA === wildB) {
            // check for negation
            var negA = a.indexOf("!") === 0;
            var negB = b.indexOf("!") === 0;
            if (negA === negB) {
                // both are negated or neither are, just return alphabetical
                return a < b ? -1 : 1;
            }
            // compare without the negatation
            var nonNegA = negA ? a.slice(1) : a;
            var nonNegB = negB ? b.slice(1) : b;
            if (nonNegA === nonNegB) {
                return negA ? 1 : -1;
            }
            return nonNegA < nonNegB ? -1 : 1;

        }
        return wildA > wildB ? -1 : 1;
    }

    return levelsA.length < levelsB.length ? -1 : 1;
}

可能有一些优化可以完成，但尚未经过广泛测试，但考虑到 unsorted_CASE2 这似乎产生了预期的结果：

unsorted_CASE2.sort(compare);

给出：

[
    "!bar/*",
    "bar/norf",
    "!bar/norf",
    "bar/x",
    "!foo/*/baz",
    "foo/qux/*",
    "foo/bar/baz",
    "!foo/qux/boo"
]

什么时候以及为什么有些项目甚至没有在排序算法中进行比较？

When and why some items don't even get compared in a sorting algorithm?

javascript

arrays

sorting

node.js

要求：

尝试次数：