这两种数组排序算法是否会为任何输入产生不同的输出

Will these two array sorting algorithms ever produce different output for any inputs?

本文关键字：输出 输入 任何 数组排序 两种 算法 是否      更新时间：2023-09-26

其中数据是以下格式的元数组，

[
  [
        "qux doo",
        "adsf",
        "abcd",
        "zzzz",
        "898jwe9"
  ],
  [
        "abcd",
        "xxrwu",
        "urnr",
        "pupupu",
        "sdsdsd"
  ]
]

对于不同的输入数据值，以下两种算法是否会产生不同的结果？

data.sort(function(a,b){
  return (JSON.stringify(a) < JSON.stringify(b)) - (JSON.stringify(a) > JSON.stringify(b));
});

data.sort(function(a, b) {
    for (var i = 0; i < Math.min(a.length, b.length); i++) {
        if (a[i] < b[i]) return -1;
        if (a[i] > b[i]) return 1;
    } 
    return (a.length > b.length) - (a.length < b.length); 
});

JSON.stringify()将转义某些字符（如双引号字符、反斜杠字符或任何控制字符），因此这些字符不太可能正确排序。

此外，由于空格的 ascii 代码低于双引号，因此如果两个数组以 "abcd " 和 "abcd" 开头，它们将无法在 JSON 中正确排序。 "abcd "应该在 "abcd" 之后，但空格的 ASCII 值低于双引号，因此它将在前面排序。 值末尾的感叹号也是如此。

如果根据您的评论，您还希望这适用于数字等非数组成员，则字符串比较不适用于比较具有不同位数的两个数字，因为1000不小于 2 ，但"1000"小于 "2" 。

另外，我建议您使用.localeCompare()来比较第二个算法中的两个字符串，因为它已经具有内置的正、负或零结果。

如果您的所有值都是字符串，或者它们通过 .toString() 正确排序，则可以使用如下.localeCompare()：

data.sort(function(a, b) {
    var comp, i;
    for (i = 0; i < Math.min(a.length, b.length); i++) {
        if ((comp = a[i].localeCompare(b[i])) !== 0) return comp;
    } 
    return (a.length > b.length) - (a.length < b.length); 
});

.localeCompare还提供了可用于区分大小写、忽略标点符号、如何处理重音字符等的选项。

根据您的评论和每个 MDN，您可以在与 Collator 对象（仅在某些浏览器中可用）进行比较时获得更好的性能。 根据文档（我自己只尝试过一次这段代码），它的工作原理是这样的：

var collater = new Intl.Collator();
data.sort(function(a, b) {
    var comp, i;
    for (i = 0; i < Math.min(a.length, b.length); i++) {
        if ((comp = collater.compare(a[i], b[i])) !== 0) return comp;
    } 
    return (a.length > b.length) - (a.length < b.length); 
});

大概必须有一些初始化或开销，可以只以这种方式完成一次。 也许他们构建了直接查找排序表。

但是浏览器对 Collator 对象的支持很少（IE 11、Chrome、没有 Firefox、没有 Safari），所以除非你在浏览器插件中使用它，所以代码只特定于一个浏览器，你必须分支它是否受支持并有两个实现。

附言如果您有大量外部数组元素，因此多次调用排序回调，它将执行得非常糟糕。 您至少可以做到每次只执行两个JSON.stringify()调用，而不是四个。

相关文章：