4

更新 2

我在排序函数中添加了权重查找，将性能和稳定性提高了大约 100%，因为之前的排序函数没有考虑所有类型，1 == "1"结果取决于数组的初始顺序，如@Esailija 指出。

这个问题的目的是改进我的这个答案，我喜欢这个问题，因为它被接受了，我觉得有一些性能可以挤出排序功能。我在这里问了这个问题，因为我没有太多线索可以从哪里开始。
也许这也让事情变得更清楚

更新

我改写了完整的问题，因为很多人说我不够具体，我尽力说明我的意思。另外，我重写了sort函数以更好地表达问题的意图。

  • 设arrayPrev为Array ( A ) ，其中A由 0 到 n 个Element s' ( E )

    • 让一个元素要么是
      • 原始类型 _
        • boolean , string , number , undefined , null
      • 对Object O的引用，其中O .type = [object Object]和O可以由
        • 0 到 n属性 P，其中P定义为Element plus
          • 对O中任何P的循环引用
        • 其中任何O可以包含 1 到 n 次。在GetReferencedName(E1) === GetReferencedName(E2)的意义上...
      • a对O的引用，其中O .type = [object Array]和O的定义类似于A
      • 对A中任何E的循环引用
  • 令 arrayCurr为与arrayPrev长度相同的Array

如下例所示

var x = {
    a:"A Property",
    x:"24th Property",
    obj: {
        a: "A Property"
    },
    prim : 1,
}
x.obj.circ = x;

var y = {
    a:"A Property",
    x:"24th Property",
    obj: {
        a: "A Property"
    },
    prim : 1,
}
y.obj.circ = y;
var z = {};

var a = [x,x,x,null,undefined,1,y,"2",x,z]
var b = [z,x,x,y,undefined,1,null,"2",x,x]    
console.log (sort(a),sort(b,a))

问题是，如何有效地对Array B进行排序，以便对 Object 的任何引用或 Primitive 的值，通过相同的compareFunction, sorted, Array A共享与以前完全相同的位置。

就像上面的例子

控制台日志

结果数组应符合规则的地方。

  • 让arrayPrev包含Element s'a和arrayCurr包含Element s'b
    1. 让arrayPrev按CompareFunction C排序。
    2. 让arrayCurr按相同的C排序。
      • 让对arrayCur排序的结果是这样的，当在位置n访问arrayCur中的E时，让n例如为 5
        • 如果E的类型是Object GetReferencedName(arrayCurr[n]) === GetReferencedName(arrayPrev[n])
        • 如果E的类型是Primitive GetValue(arrayCurr[n]) === GetValue(arrayPrev[n])
        • 即b[n] === a[n]例如b[5] === a[5]
      • 这意味着所有元素都应按类型分组，并按值排序。
      • 在C中对函数 F的任何调用至少应在 ES5 之前实现，这样就可以在不需要任何 shim 的情况下提供兼容性。

我目前的方法是在 arrayPrev 中标记对象，以便在arrayCurr中对它们进行相应的排序，然后再次删除标记。但这似乎没有那么有效。这是当前sort使用的函数。

function sort3 (curr,prev) {
         var weight = {
            "[object Undefined]":6,         
            "[object Object]":5,
            "[object Null]":4,
            "[object String]":3,
            "[object Number]":2,
            "[object Boolean]":1
        }
        if (prev) { //mark the objects
            for (var i = prev.length,j,t;i>0;i--) {
                t = typeof (j = prev[i]);
                if (j != null && t === "object") {
                     j._pos = i;   
                } else if (t !== "object" && t != "undefined" ) break;
            }
        }

        curr.sort (sorter);

        if (prev) {
            for (var k = prev.length,l,t;k>0;k--) {
                t = typeof (l = prev[k]);
                if (t === "object" && l != null) {
                    delete l._pos;
                } else if (t !== "object" && t != "undefined" ) break;
            }
        }
        return curr;

        function sorter (a,b) {

             var tStr = Object.prototype.toString
             var types = [tStr.call(a),tStr.call(b)]
             var ret = [0,0];
             if (types[0] === types[1] && types[0] === "[object Object]") {
                 if (prev) return a._pos - b._pos
                 else {
                     return a === b ? 0 : 1;
                 }
             } else if (types [0] !== types [1]){
                     return weight[types[0]] - weight[types[1]]
             }



            return a>b?1:a<b?-1:0;
        }

    }

这是一个Fiddle和一个JSPerf （随意添加你的代码片段）
和旧的Fiddle

4

4 回答 4

2

从描述中，您似乎可以简单地使用排序功能：

function sortOb(a,b){a=JSON.stringify(a);b=JSON.stringify(b); return a===b?0:(a>b?1:-1);}
var x = {a:1};
var y = {a:2};

var a = [1,x,2,3,y,4,x]
var b = [1,y,3,4,x,x,2]

a.sort(sortOb);
b.sort(sortOb);
console.log (a,b);
于 2013-06-06T18:18:59.707 回答
2

如果您知道数组包含相同的元素（重复次数相同，可能顺序不同），那么您可以将旧数组复制到新数组中，如下所示：

function strangeSort(curr, prev) {
    curr.length = 0;             // delete the contents of curr
    curr.push.apply(curr, prev); // append the contents of prev to curr
}

如果您不知道数组包含相同的元素，那么按照您的要求去做是没有意义的。

从您链接的内容来看，您可能正在尝试确定数组是否包含相同的元素。在这种情况下，您要问的问题并不是您要问的问题，基于排序的方法可能根本不是您想要的。相反，我推荐一种基于计数的算法。

  1. 比较数组的长度。如果它们不同，则数组不包含相同的元素；返回假。如果长度相等，继续。
  2. 遍历第一个数组并将每个元素与您看到它的次数相关联。既然ES6 Maps存在，Map 可能是跟踪计数的最佳方式。如果您不使用 Map，则可能需要或方便地以不同方式维护不同数据类型的项目的计数。（如果您通过赋予对象新属性来维护对象的计数，请在返回之前删除新属性。）
  3. 遍历第二个数组。对于每个元素，
    1. 如果没有记录元素的计数，则返回 false。
    2. 如果元素的计数为正，则将其减 1。
    3. 如果元素的计数为 0，则该元素在第二个数组中出现的次数比在第一个数组中出现的次数多。返回假。
  4. 返回真。

如果达到第 4 步，则每个项目在第一个数组中出现的次数至少与在第二个数组中出现的次数一样多。否则，它会在步骤 3.1 或 3.3 中检测到。如果任何项目在第一个数组中出现的次数多于在第二个数组中出现的次数，则第一个数组会更大，并且算法会在步骤 1 中返回。因此，数组必须包含相同元素且重复次数相同。

于 2013-06-19T03:57:39.760 回答
1

您的函数始终返回 的副本sort.el，但您可以更轻松：

var sort = (function () {
    var tmp;

    function sorter(a, b) {
        var types = [typeof a, typeof b];
        if (types[0] === "object" && types[1] === "object") {
            return tmp.indexOf(a) - tmp.indexOf(b); // sort by position in original
        }
        if (types[0] == "object") {
            return 1;
        }
        if (types[1] == "object") {
            return -1;
        }
        return a > b ? 1 : a < b ? -1 : 0;
    }


    return function (el) {
        if (tmp) {
            for (var i = 0; i < el.length; i++) {
                el[i] = tmp[i]; // edit el in-place, same order as tmp
            }
            return el;
        }
        tmp = [].slice.call(el); // copy original
        return tmp = el.sort(sorter); // cache result
    };

})();

请注意，我用 and 替换sort.el了tmp一个闭包。小提琴：http: //jsfiddle.net/VLSKK/

编辑：这个（以及你原来的解决方案）

  • 仅当数组包含相同元素时才有效。
  • 维护不同对象的顺序a

但

  • 调用两次以上时不会搞砸
于 2013-06-06T19:52:12.370 回答
-1

试试这个

function ComplexSort (a, b)
{
     if(typeof a == "object") { 
        a = a.a; 
    } 
    if(typeof b == "object") { 
       b = b.a;
    } 
    return a-b;
}

var x = {a:1};
var y = {a:2};

var a = [1,x,2,3,y,4,x]
var b = [1,y,3,4,x,x,2]

a.sort(ComplexSort);
b.sort(ComplexSort);
console.log ("Consistent", a,b);
于 2013-06-06T18:22:09.063 回答