# 08 洗牌算法实现数组乱序

关于 JavaScript 数组乱序的方法有多种实现方式，或者借助一些第三方开源工具库如 loadsh 也可以轻松实现，然而要做到数组足够的无规律乱序也非易予，还是有一些要点需要考虑。

## sort 方法

最简单的便是使用 sort 函数，代码如下：

```javascript
const shuffle = arr => {
  arr.sort(() => Math.random() > 0.5)
  return arr
}
```

在一般场景中以上代码实现便可满足功能需求，但仅是使用 sort 函数的乱序方式并不完美，出于 v8 引擎的底层原因，它对长短数组采用不同的排序方式，并不能真正随机打乱数组排序，简而言之就是最后得到的数组不能足够乱。

> 由于 v8 引擎出于对性能的考虑，sort 函数对短数组（长度小于 10）使用的是插入排序，对长数组则使用了快速排序。其实不管用什么排序方法，大多数排序算法的时间复杂度介于 O(n) 到 O(n2) 之间，元素之间的比较次数通常情况下要远小于 n(n-1)/2，也就意味着有一些元素之间根本就没机会相比较（也就没有了随机交换的可能），这使 sort 随机排序的算法自然也不能真正随机。通俗的说，其实我们使用 array.sort 进行乱序，理想的方案或者说纯乱序的方案是：数组中每两个元素都要进行比较，这个比较有 50% 的交换位置概率。如此一来，总共比较次数一定为 n(n-1)。而在 sort 排序算法中，大多数情况都不会满足这样的条件。因而当然不是完全随机的结果了。

## Fisher–Yates Shuffle 洗牌算法

Fisher–Yates Shuffle 洗牌算法是目前业界最著名的数组乱序算法之一，并且能够使数组足够乱，实现如下：

```javascript
const shuffle = arr => {
  let i = arr.length
  let j
  while (i) {
    j = Math.floor(Math.random() * i--)
    ;[arr[i], arr[j]] = [arr[j], arr[i]]
  }
  return arr
}
```

关于更多洗牌算法的细节详见 [Fisher–Yates Shuffle](https://bost.ocks.org/mike/shuffle/)，里面通过动画生动地介绍了洗牌算法地高效乱序实现方式。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://chanshiyu.gitbook.io/blog/qian-duan/javascript/08-xi-pai-suan-fa-shi-xian-shu-zu-luan-xu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.