在JavaScript中，反转数组的最高效方法是什么？

Question

最近有人问我在JavaScript中反转数组的最有效方法是什么。目前，我建议使用for循环和调整数组，但后来意识到还有一个本地的Array.reverse()方法。

出于好奇的目的，有人能帮助我通过示例或指导我正确的方向，使我能够深入了解吗？关于如何衡量性能的任何建议也将非常棒。

- luisgo

---

未来的读者注意：本帖中的大多数答案效率低下（二次方程式），难以阅读、存在漏洞或完全不正确。使用时应极度谨慎！我已保护了这个问题（因过于宽泛而不适合主题），以避免出现更多低质量的回复。很多性能结论和基准测试已经过时或不正确。那些有关闭/删除投票权的人，我强烈建议清除该线程！ - ggorlen

Answer 1

基于这个设置：

var array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
var length = array.length;

Array.reverse(); 是最慢的第一或第二个方法!

这里有基准测试:

https://jsperf.com/js-array-reverse-vs-while-loop/9

在各个浏览器中，交换循环更快。有两种常见的交换算法（参见 Wikipedia），每种算法都有两种变体。

这两种交换算法是临时交换和XOR交换。

两种变体处理索引计算的方式不同。第一个变体比较当前左侧索引和数组右侧索引，然后将数组右侧索引递减。第二个变体比较当前左侧索引和长度除以二，然后为每次迭代重新计算右侧索引。

您可能会看到两种变体之间存在很大差异，也可能不会。例如，在Chrome 18中，临时交换和XOR交换的第一个变体比第二个变体慢60%以上，但在Opera 12中，临时交换和XOR交换的两种变体性能相似。

临时交换：

第一个变体：

function temporarySwap(array)
{
    var left = null;
    var right = null;
    var length = array.length;
    for (left = 0, right = length - 1; left < right; left += 1, right -= 1)
    {
        var temporary = array[left];
        array[left] = array[right];
        array[right] = temporary;
    }
    return array;
}

第二种变化：

function temporarySwapHalf(array)
{
    var left = null;
    var right = null;
    var length = array.length;
    for (left = 0; left < length / 2; left += 1)
    {
        right = length - 1 - left;
        var temporary = array[left];
        array[left] = array[right];
        array[right] = temporary;
    }
    return array;
}

---

XOR 交换：

第一种变体：

function xorSwap(array)
{
    var i = null;
    var r = null;
    var length = array.length;
    for (i = 0, r = length - 1; i < r; i += 1, r -= 1)
    {
        var left = array[i];
        var right = array[r];
        left ^= right;
        right ^= left;
        left ^= right;
        array[i] = left;
        array[r] = right;
    }
    return array;
}

第二种变化：

function xorSwapHalf(array)
{
    var i = null;
    var r = null;
    var length = array.length;
    for (i = 0; i < length / 2; i += 1)
    {
        r = length - 1 - i;
        var left = array[i];
        var right = array[r];
        left ^= right;
        right ^= left;
        left ^= right;
        array[i] = left;
        array[r] = right;
    }
    return array;
}

---

还有一种名为解构赋值的交换方法：

http://wiki.ecmascript.org/doku.php?id=harmony:destructuring

解构赋值:

第一个变化:

function destructuringSwap(array)
{
    var left = null;
    var right = null;
    var length = array.length;
    for (left = 0, right = length - 1; left < right; left += 1, right -= 1)
    {
        [array[left], array[right]] = [array[right], array[left]];
    }
    return array;
}

第二个变体：

function destructuringSwapHalf(array)
{
    var left = null;
    var right = null;
    var length = array.length;
    for (left = 0; left < length / 2; left += 1)
    {
        right = length - 1 - left;
        [array[left], array[right]] = [array[right], array[left]];
    }
    return array;
}

现在，使用解构赋值的算法是其中最慢的。它甚至比Array.reverse();还要慢。然而，使用解构赋值和Array.reverse();方法的算法是最简短的例子，并且它们看起来最干净。我希望它们的性能在未来会得到改善。

---

另一个需要提到的是，现代浏览器正在改进其数组push和splice操作的性能。

在Firefox 10中，使用数组push和splice的for循环算法与临时交换和XOR交换的循环算法不相上下。

for (length -= 2; length > -1; length -= 1)
{
    array.push(array[length]);
    array.splice(length, 1);
}

然而，在许多其他浏览器的数组push和splice性能匹配或超过之前，你应该考虑坚持使用交换循环算法。

- XP1

---

我认为应该注意到，上述所有功能（临时交换除外）仅适用于整数数组，而不适用于其他类型的数组（字符串、对象等）。 - DisgruntledGoat

您的基准测试中的“先推后切”测试破坏了全局变量 length，导致其后的所有测试都失去了意义。 - Boris Zbarsky

鲍里斯是正确的：http://jsperf.com/js-array-reverse-vs-while-loop/9。 此外，在Google Chrome中，使用array.reverse方法要比其他方法更快。 - Ivan Castellanos

是的，在2016年的Google Chrome中，array.reverse的速度至少比其他任何东西快两倍。请查看其他评论中的jsperf链接。 - Max

这些代码建议质量很差（像ANSI C一样编写），而且基准测试也是不正确的。不要过早地进行优化，如果您想要原地操作，请使用内置的array.reverse()，如果您想要复制，请使用array.slice().reverse()。标准库已经很可能是最快的，无疑是最干净易懂的，并且随着时间的推移它们的速度会自动提高。 - ggorlen

Answer 2

你可以简单地使用 map 进行此操作。

let list = [10, 20, 30, 60, 90]
let reversedList = list.map((e, i, a)=> a[(a.length -1) -i]) // [90, 60...]

- Srinivas Damam

---

这是一种不改变原始数组的解决方案！+1 - Peter Albert

Answer 3

本地方法总是更快的。

因此，在可能的情况下使用Array.reverse。否则，一个运行时间复杂度为O(1)的实现会更好 ;)

否则就使用类似这样的东西。

var reverse = function(arr) {
   var result = [],
       ii = arr.length;
   for (var i = ii - 1;i !== 0;i--) {
       result.push(arr[i]);
   }
   return result;
}

基准测试！

有趣的是，如果您使用for循环的所有三个阶段而不仅仅是其中一个，则速度会更快。

for(var i = ii - 1; i !== 0; i--)比var i = ii - 1; for(; i-- !== 0;)更快。

- Raynos

---

@Matt McDonald 很有趣，我们刚在大学里完成了一个证明相反的项目。虽然我们测试了各种功能，如冒泡排序、堆排序、快速排序等。这些东西的时间性能很大程度上取决于数组的布局方式。（它是否已经排序，是否已经随机？）不同类型的排序/反向排序通常取决于数组的初始状态。很难证明哪个是最快的，因为有许多不同的情况。 - clamchoda

改进你的算法，然后再试一次。现在，Array.reverse(); 是最慢的第一或第二个！ - XP1

在JavaScript中，由于语言的设计根本上存在缺陷，因此本地方法几乎总是较慢的。请参阅bind vs. closure; for loop versus map; for versus .forEach。这是因为内置方法无法像您一样做出关于数组的假设，因此必须执行更多的测试。如果您关心性能，请考虑自己编写循环或使用lodash；而对于可读性较好的代码，可以使用本地方法。 - Brian M. Hunt

@Raynos的例子有问题；它没有遍历整个数组。应该改为var i = ii - 1;i >= 0;i--。 - mcNux

当数组为空时，for (var i = ii - 1;i !== 0;i--) {会导致无限循环。ii = arr.length;是一个无意义的变量。这是粗糙的代码，请避免使用。"否则最好运行在O(1)的实现 ;)"是不可能的和令人困惑的，我认为这是一个玩笑，因为有眨眼的表情符号，但为什么呢？"for(var i = ii - 1; i !== 0;i--)比var i = ii - 1;for(;i-- !== 0;)更快"只是错误的基准测试--初始化和递减是在循环初始化器内部还是外部都没有关系。 - ggorlen

Answer 4

我提交了一个有关Firefox反转性能缓慢的bug。Mozilla的一位工作人员查看了已接受帖子中使用的基准测试，并表示它非常误导人，根据他们的分析，本机方法通常更适合反转数组。（这是应该的！）

- starwed

---

如果人们对这个话题感兴趣，他们需要阅读整个错误案例。自从你发布了你的答案以来，似乎还有更多的内容，但我认为肯定会坚持使用本地的Array.reverse()。 - CWSpear

Answer 5

这是使用三元运算符来反转数组的最有效和清洁的方式。

function reverse(arr) {
  return arr.length < 2 ? arr : [arr.pop()].concat(reverse(arr));
}
console.log(reverse([4, 3, 3, 1]));

- Arslan shakoor

---

这根本不高效 - 它是二次的（在循环中调用concat，基本上为每个递归调用重新分配和构建整个结果数组），如果由于递归而数组太大，则会导致堆栈溢出（尝试使用reverse(Array(10000).fill(0))）。 - ggorlen

Answer 6

您可以使用.slice().reverse()来完成此操作：

const yourArray = ["first", "second", "third", "...", "etc"];
const reversedArray = yourArray.slice().reverse();
console.log(reversedArray);

请注意，.slice() 的使用是为了防止修改 yourArray，因为 .reverse() 是原地操作的。

- Kangudie Muanza - Killmonger

---

这里使用.slice()是多余的！ - Jayesh Chandrapal

@JayeshChandrapal 不是这样的。 .reverse() 会改变参数，因此 slice 可以防止修改 yourArray。 - ggorlen

Answer 7

交换函数是最快的。这是我写的一个反转函数，与上面提到的交换函数略有相似但执行速度更快。

function reverse(array) {
  var first = null;
  var last = null;
  var tmp = null;
  var length = array.length;

  for (first = 0, last = length - 1; first < length / 2; first++, last--) {
    tmp = array[first];
    array[first] = array[last];
    array[last] = tmp;
  }
}

您可以在这里找到基准测试结果：http://jsperf.com/js-array-reverse-vs-while-loop/19。该测试与JavaScript数组反转和while循环相关。

- Brice Lin

Answer 8

由于没有人提出来，并为了完成反转数组的方法列表...

array.sort(function() {
    return 1;
})

它比两种while方法都快两倍，但除此之外，速度非常慢。

http://jsperf.com/js-array-reverse-vs-while-loop/53

- CodeManX

---

它不会翻转数组；也许它曾经这样做，但这取决于实现。我现在在最新的稳定版V8中测试了它，它没有翻转数组。实际上，顺序保持不变。然而，当我返回-1时，它会翻转数组。这可能是因为在ES2019中，.sort方法需要执行稳定排序。但是，我仍然不会依赖于此。 - pepkin88

有趣。这可能取决于用于排序的算法，因此它基本上是实现特定的。只要每个元素仅被访问一次，-1应该可以反转顺序，而1则保持当前顺序。否则它将是任意的。 - CodeManX

排序的时间复杂度为O(n log(n))，但反转的时间复杂度为O(n)。这种方法不具有可扩展性，并且似乎与实现相关，正如上面所提到的。在Chrome 94中对我来说是失败的。即使它能够工作并且效率高，最好也是完全令人困惑和不符合语义学的：sort(() => 1)如何向代码读者传达“反转数组”的含义？ - ggorlen

Answer 9

这里有另一个例子，可以永久修改数组并反转它的元素：

var theArray = ['a', 'b', 'c', 'd', 'e', 'f'];

function reverseArrayInPlace(array) {
  for (var i = array.length - 1; i >= 0; i -= 1) {
    array.push(array[i]);
  }
  array.splice(0, array.length / 2);
  return array;
};
reverseArrayInPlace(theArray);
console.log(theArray); // -> ["f", "e", "d", "c", "b", "a"]

- drjorgepolanco

Answer 10

另一个建议，与上面类似，但使用splice：

var myArray=["one","two","three","four","five","six"];
console.log(myArray);
for(i=0;i<myArray.length;i++){
myArray.splice(i,0,myArray.pop(myArray[myArray.length-1]));
}
console.log(myArray);

- SlavCo Zute

---

.pop()不需要任何参数。此外，for(i=0)声明了一个全局变量，可能会导致错误。请使用var/let/const。 - ggorlen