javascript - 原生排序方法如何处理稀疏数组

Question

当对稀疏数组进行排序时 [5, 2, 4, , 1].sort() -> [1, 2, 4, 5, empty]，空值总是排在最后即使有回调，无论 return 语句如何。

作为挑战，我正在构建自己的排序方法，我通过使用过滤器方法解决了这个问题，因为过滤器会跳过空值。然后迭代过滤后的数组并将原始数组的索引设置为过滤后的数组的值。然后我缩短了原始数组的长度，因为剩余的项目将是重复的，我终于可以将它提供给我的排序算法。完成后，我将其长度设置回原始长度，最后添加适量的空项。这是一段代码，但这里是 a link of the entire code

const collectUndefined = [];

// remove empty items and collect undefined
const removeSparse = this.filter(el => {
  if (el === undefined) {
    collectUndefined.push(el);
  }

  return el !== undefined;
});

const tempLength = this.length;

// reset values but will contain duplicates at the end
for (let i = 0; i < removeSparse.length; i++) {
  this[i] = removeSparse[i];
}

// shorten length which will remove extra duplicates
this.length = removeSparse.length;



// sort algorithm ...



// place undefineds back into the array at the end
this.push(...collectUndefined);

// restores original length and add empty elemnts at the end
this.length = tempLength;
return this

在处理稀疏数组时，原生排序是以这种类似的方式实现的，还是没有。

Answer 1

说到Array.sort的实现你还要问是哪个引擎？它们在如何最终得到数组的最终排序版本方面并不完全相同。例如，V8 在执行any 排序之前有一个预处理和后处理步骤:

V8 has one pre-processing step before it actually sorts anything and also one post-processing step. The basic idea is to collect all non-undefined values into a temporary list, sort this temporary list and then write the sorted values back into the actual array or object. This frees V8 from caring about interacting with accessors or the prototype chain during the sorting itself.

您可以找到关于 V8 经历 here 的整个过程的非常详细的解释

V8 排序的实际源代码(使用 Timsort )可以是 found here现在在 Torque语言。

V8 Array.sort 的 js 测试可以是 seen here

然而，最重要的是实际上没有从原始数组中删除任何内容，因为它不应该被删除。排序不应改变 原始数组。如果您调用 myArray.sort() 并且突然间它的 8 个元素少了 5 个元素(例如)，那将是 super 奇怪的。这不是您在任何 Array.sort 规范中都能找到的东西。

此外，Array.sort 密切关注其排序的类型并对其进行特定排序。示例:

let arr = [4,2,5,,,,3,false,{},undefined,null,0,function(){},[]]

console.log(arr.sort())

请注意在上面的输出中，array 是第一个，然后是 numeric 值、object literal、Boolean , function, null 然后是 undefined/empty。因此，如果您想要真正匹配规范，则必须考虑不同类型的排序方式。