Array.prototype.sort暂时复制内容？

Question

我最近想告诉某人如何Array.prototype.sort使用自定义方法在任何给定时间比较两个值,并决定是应该交换它们还是单独使用它们.我决定在每次比较期间记录数组,以便可以看到之前比较的结​​果.当我记录数组时,我注意到在某些时刻阵列的状态有些奇怪.

假设如下:

var num = [ 2, 1, 8, 5, 3 ];

num.sort( comparator );

function comparator ( a, b ) {
    console.log( num ); // Current state of num
    return a - b; // Order values numerically
}

这是输出:

[ 2, 1, 8, 5, 3 ] // Comparing 2 and 1
[ 1, 2, 8, 5, 3 ] // Comparing 2 and 8
[ 1, 2, 8, 5, 3 ] // Comparing 8 and 5
[ 1, 2, 8, 8, 3 ] // Comparing 2 and 5
[ 1, 2, 5, 8, 3 ] // Comparing 8 and 3
[ 1, 2, 5, 8, 8 ] // Comparing 5 and 3
[ 1, 2, 5, 5, 8 ] // Comparing 2 and 3

数组已正确排序([ 1, 2, 3, 5, 8 ])但我仍然在集合本身的一些传递中摸不着头脑.

8如何在迭代4中出现两次,暂时替换为5.再次,8出现两次两次迭代,之后暂时替换3次.最后,5出现两次,在最后一次迭代中暂时替换3.

请注意,上面的代码是在Chrome中运行的.

Answer 1

有趣，但并不太令人惊讶。

在本例中，它似乎使用了简单的插入排序算法。

大致如下：

• 获取物品[1]
• 将其下方的每个项目向上移动一个，直到找到较低的项目，然后将其放在该项目的上方
• 获取物品[2]
• 将其下方的每个项目向上移动一个，直到找到较低的项目，然后将其放在该项目的上方
• 获取物品[3]
• （续）

在描述冒泡排序算法时，您通常会想象每个元素沿着数组交换，直到找到它的位置。但将项目存储到临时变量中比交换它更有效。