打乱数组中的元素

问题

打乱数组中的元素。

解决方案

Fisher-Yates shuffle是一种高效、公正的方式来让数组中的元素随机化。这是一个相当简单的方法：在列表的结尾处开始，用一个随机元素交换最后一个元素列表中的最后一个元素。继续下一个并重复操作，直到你到达列表的起始端，最终列表中所有的元素都已打乱。这Fisher-Yates shuffle Visualization可以帮助你理解算法。

shuffle = (source) ->
  # Arrays with < 2 elements do not shuffle well. Instead make it a noop.
  return source unless source.length >= 2
  # From the end of the list to the beginning, pick element `index`.
  for index in [source.length-1..1]
    # Choose random element `randomIndex` to the front of `index` to swap with.
    randomIndex = Math.floor Math.random() * (index + 1)
    # Swap `randomIndex` with `index`, using destructured assignment
    [source[index], source[randomIndex]] = [source[randomIndex], source[index]]
  source

shuffle([1..9])
# => [ 3, 1, 5, 6, 4, 8, 2, 9, 7 ]

讨论

错误的方式

有一个很常见但是错误的打乱数组的方式：通过随机数。

shuffle = (a) -> a.sort -> 0.5 - Math.random()

如果做一个随机的排序，应该得到一个序列随机的顺序,微软也用这种随机排序算法 。 随机排序算法产生有偏差的结果 ，因为它存在一种洗牌的错觉。 随机排序会导致序列排序质量的参差不齐,不会导致一个工整的洗牌。

速度和空间的优化

以上的解决方案处理速度是不一样的。该列表，当转换成JavaScript时，比它要复杂得多，变性分配比处理裸变量的速度要慢得多。以下代码并不完善，并且需要更多的源代码空间 … 但会编译量更小，运行更快：

shuffle = (a) ->
  i = a.length
  while --i > 0
    j = ~~(Math.random() * (i + 1)) # ~~ is a common optimization for Math.floor
    t = a[j]
    a[j] = a[i]
    a[i] = t
  a

扩展 Javascript 来包含乱序数组 下面的代码将乱序功能添加到数组原型中，意味着可以在任何希望的数组中运行它，并以更直接的方式来运行它。

Array::shuffle ?= ->
  if @length > 1 then for i in [@length-1..1]
    j = Math.floor Math.random() * (i + 1)
    [@[i], @[j]] = [@[j], @[i]]
  this

[1..9].shuffle()
# => [ 3, 1, 5, 6, 4, 8, 2, 9, 7 ]