用于基于另一个部分列表的排序来排序列表的算法

Question

在订单列表不包含列表中使用的所有密钥的意义上,该问题与基于另一列表的顺序对列表进行排序的主题的其他问题不同.

说我有一个清单[a, b, c, d, e]和我的订单清单[b, d, e].

现在我将订单列表更改为[b, e, d].是否有一个相对简单的算法来采用原始列表？假设最终排序是否为[a, b, e, c, d]或者[a, b, c, e, d],并且顺序列表将始终是原始列表的子集,这并不重要.

编辑:从我的例子中清除关于最终排序的一些问题:e被命令在b和之间d,并且在排序列表中,如果e最终与b或相邻则无关紧要d.但是,例如,如果由于这种分类a转移到后b- 虽然合法订购 - 这是不可取的.

Answer 1

编辑这是一个稍微更有效的版本；与其在每次迭代中查找订单元素的索引 (arr.indexOf)，只需在开始时查找一次以保持索引更新即可。

如果 N 是数组的长度，M 是订单的长度，最糟糕的时间是 O(N * M + M^2)

function partialSort(arr, order) {
    var orderIndex = [];
    for(var i = 0; i < order.length; i++) {
        orderIndex[i] = arr.indexOf(order[i]);
    }
    for(var i = 0; i < orderIndex.length; i++) {
        var indexI = orderIndex[i];
        for(var j = i + 1; j < orderIndex.length; j++) {
            var indexJ = orderIndex[j];
            if(indexI > indexJ) {
                var temp = arr[indexI];
                arr[indexI] = arr[indexJ];
                arr[indexJ] = temp;
                orderIndex[i] = indexJ;
                orderIndex[j] = indexI;
                indexI = indexJ;
            }
        }
    }
    return arr;
}
var a = [1, 2, 3, 4, 5, 6, 7];
var o = [3,5,7];
console.log(o + "\n" + partialSort(a, o));
o = [5,3,7];
console.log(o + "\n" + partialSort(a, o));
o = [7,3,5];
console.log(o + "\n" + partialSort(a, o));

这是使用 MlogM 排序的版本 O(N * M + M * log(M) + M)

function partialSort(arr, order) {
    var orderIndex = [];
    for(var i = 0; i < order.length; i++) {
        orderIndex[i] = arr.indexOf(order[i]);
    }
    // sort by index ~some quick sort variant O(M * log(M))
    orderIndex.sort(function(a, b) { return a - b; });
    // put the ordered elements in the correct sequence in the main array
    for(var i = 0; i < orderIndex.length; i++) {
        arr[orderIndex[i]] = order[i];
    }
    return arr;
}

如果你想要绝对最佳的效率，你可以用基数排序替换orderIndex.sort O(N * M + M + M)