以前面试的时候考过洗牌算法，过后写的比拟简陋，外围思路如下：
- 创立一个空的后果数组；
- 顺次从原数组中随机取样，而后按程序
push到后果数组中； - 为防止出现碰撞，每次取样后，将该元素从原数组删除；
其实还有一种思路，按程序从原数组中获取元素，而后放到新数组的随机地位，然而这样无奈打消碰撞的问题
function shuffle(arr) { let len = arr.length; let res = []; for (let i=0; i<len; i++) { res.push(sample(arr)); } return res;}function sample(arr) { // 数组随机取样 let randIndex = Math.floor(Math.random() * arr.length); // 获取元素并从原数组中删除 let [ele] = arr.splice(randIndex, 1); return ele;}能够看到下面的代码存在两个问题：
- 创立新数组，导致应用了额定空间；
- 从数组中删除元素须要挪动其余元素下标，导致总的工夫复杂度为
O(n^2)；
那么有没有一种办法能够不创立新数组，间接在原数组上批改呢？明天看到一种 Fisher-Yates 洗牌算法，思路与下面代码相似，但没有创立新数组，而是采纳了与快排相似的元素替换办法:
- 从数组最初一个元素开始倒序遍历；
- 从蕴含以后元素在内的数组中，随机抽取元素，与以后元素替换；
- 一直往前遍历，直到所有元素都被替换；
function randomIndex(index: number): number { return Math.floor(Math.random() * (index + 1));}function swap<T>(arr: T[], a: number, b: number) { let temp = arr[a]; arr[a] = arr[b]; arr[b] = temp;}export function shuffle<T>(arr: T[]): T[] { for (let i=arr.length-1; i>=0; i--) { let r = randomIndex(i); swap<T>(arr, r, i); } return arr;}const res = shuffle<number>([1, 2, 3, 4, 5, 6]);console.log(res);从代码中能够看出，每一步都是从数组中随机抽取元素，放到数组的最初，而后指针后退一位，持续从剩下数组中抽取元素，放到数组的最初。按这个过程依此类推，最终整个数组的元素就被打乱了。实现的思路其实和自己之前的代码是一样的，然而有两点改良：
- 没有创立新数组，空间复杂度为
O(n)； - 通过元素替换的办法，防止了从数组中删除元素导致须要挪动其余元素下标的问题，工夫复杂度为
O(n)；