5

我最近想向某人介绍如何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 中运行的。

4

1 回答 1

2

很有趣，但也不会太令人惊讶。

在这种情况下，它似乎使用了一种简单的插入排序算法。

类似于以下内容：

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

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

于 2013-10-08T21:50:47.117 回答