突然发现我的知识盲区好像有点大
这里记录三种常用的洗牌算法。

Fisher-Yates洗牌算法

 核心思想是创建一个新数组，每次从原数组中选一个之前没有选过的元素加入到新数组的末尾。
 一眼就能看懂的东西就直接上代码了：（C#）

public List<int> Fisher_Yates_Shuffle(List<int> originList)
{
    List<int> returnList = new List<int>();//创建一个新数组用于存储打乱后的数据
    var rand = new Random();//通过Random类的实例获取随机数
    while (originList.Count > 0)
    {
        int randNum = rand.Next(0, originList.Count);//Random.Next()方法,在左闭右开区间内生成随机整数。
        int numToAdd = originList[randNum];
        originList.RemoveAt(randNum);
        returnList.Add(numToAdd);
    }
    return returnList;
}

代码也是一眼就能看懂。
&emsp;由于使用数组（List底层是数组）实现，所以总体时间复杂度是O(n2)，而由于使用了一个最大长度与原来数组相等的数组，所以空间复杂度是O(n)。

&emsp;对原数组中每一个元素都能等概率地出现在新数组中每一个位置的证明：
&emsp;元素m被放置在i位置的概率，即为元素m没有被放置在前i-1个位置的概率乘以放置元素在第i个位置时选中元素m的概率。
&emsp;元素m不被放置在第一个位置的概率为 $\frac{n-1}{n}$（最初共有n个元素，除了元素m之外还有n-1个元素。），不被放置在第2个位置的概率为$\frac{n-2}{n-1}$，以此类推，不被放置在第i-1个位置的概率为$\frac{n-(i-1)}{n-(i-1)+1}$，被放置在第i个位置的概率为$\frac{1}{n-(i-1)}$（选中元素m前已经选走了i-1个元素，还剩n-(i-1)个元素），将这些概率相乘则得到元素m被放置在位置i的概率为$\frac{1}{n}$。
&emsp;手写笔记：（字比较丑，图一乐）
笔记FisherYates

Knuth-Durstenfeld洗牌算法

&emsp;Fisher-Yates算法使用了额外空间来存储打乱后的数组，导致算法的空间复杂度为O(n)，而Knuth-Durstenfeld算法原地修改输入数组，将空间复杂度降低到了O(1)。
&emsp;核心思想是将数组划分为有序区和打乱区两个部分（为了描述方便，我们暂且认为打乱前的数组是有序的），有序区在打乱区的前面。在数组被打乱之前，整个数组都是有序区。每次，在有序区中随机选择一个元素，将其与有序区的末尾元素交换，直到整个数组都是打乱区。
&emsp;代码如下：（C#）

public int[] Knuth_Durstenfeld_Shuffle(int[] originNums)
{
    var rand = new Random();
    for (int i = originNums.Length - 1; i >= 0; i--)
    {
        int randNum = rand.Next(0, i + 1);
        //交换这两个数
        int temp = originNums[randNum];
        originNums[randNum] = originNums[i];
        originNums[i] = temp;
    }
    return originNums;
}

&emsp;我最初实现这个算法的时候犯蠢了，因为最近力扣搁那整异或周，导致我在交换两个数的时候用了a^=b;b^=a;a^=b的方法，但是这里randNum是可以等于i的（否则原来的最后一个数必定不在最后），结果就成了a^=a;a^=a;a^=a，然后结果就变成了0。
&emsp;这个算法除了改进了Fisher-Yates算法的空间复杂度，还顺便把时间复杂度也给改进了，因为这个算法中不再进行数组的插入和删除。时间复杂度为O(n)。

&emsp;对原数组中每一个元素都能等概率地出现在新数组中每一个位置的证明：
&emsp;先上图方便说明，假设数组长度为n：
笔记KnuthDurstenfeld
&emsp;首先对于元素4，出现在每一个位置的概率都是$\frac{1}{n}$，这很容易理解；
&emsp;然后对于元素3，出现在位置4（即数组末尾的那个位置）的概率即为元素4选中元素3的概率$\frac{1}{n}$，而出现在位置3以及之前的概率为元素4没有选中元素3的概率乘以$\frac{n-2}{n-1}$（元素3以及之前元素的长度为n-1），也是$\frac{1}{n}$；
&emsp;然后对于元素2，出现在位置4的概率为$\frac{1}{n}$，出现在位置3的概率为元素4没有选到元素2的概率乘以元素3选到元素2的概率，即$\frac{n-1}{n}$*$\frac{1}{n-1}$=$\frac{1}{n}$，出现在位置2以及之前的概率同样为$\frac{1}{n}$，其他元素以此类推。实际上虽然实现略有不同，但是证明思路以及写出来的计算式和Fisher-Yates算法是完全一致的。（毕竟是它的改进版本）

Inside-Out洗牌算法

&emsp;前两种洗牌算法都有一个共性，就是会改变输入的数组（当然Knuth-Durstenfeld算法可以在方法内复制一个数组从而避免对输入数组的修改，但是人家核心思想就是原地修改…），在有些情况下，我们需要保留输入的数组，使用Inside-Out洗牌算法可以解决这个问题。
&emsp;核心思想是先创建一个原数组的复制（毕竟要保留原数组），然后使用类似Knuth-Durstenfeld算法的思路，将数组的前面部分视为打乱区，后面没有处理过的部分视为有序区，每次将有序区的第一个元素与打乱区的随机一个元素交换，然后打乱区大小+1，实现上其实就是Knuth-Durstenfeld算法的反向版本，但是由于Inside-Out算法从前往后扫描数组，所以如果数组以数据流的形式传入，或者无法读取数组长度时，只能使用这种算法，而前两种算法无法使用。
&emsp;代码如下：(C#)

public int[] Inside_Out_Shuffle(int[] originNums)
{
    int[] resultArr = new int[originNums.Length];
    Array.Copy(originNums, resultArr, originNums.Length);
    var rand = new Random();
    for(int i = 0; i < originNums.Length; i++)
    {
        int randNum = rand.Next(0, i + 1);
        resultArr[i] = resultArr[randNum];
        resultArr[randNum] = originNums[i];//扩展打乱区后，将刚加入打乱区的数和打乱区内的随机一个数交换。
        //借用原数组i位置的元素就不需要使用临时变量来处理数字交换了（
    }
    return resultArr;
}

&emsp;时间复杂度为O(n)，空间复杂度为O(n)。
&emsp;证明和Knuth-Durstenfeld算法完全一致。
&emsp;笔记图一乐。
笔记Inside-Out

不知道名字的算法

&emsp;当年写俄罗斯方块7Bag的时候在网上学了这个算法：

private List<T> RandomSort<T>(List<T> list) {//这会返回一个顺序被打乱的List且不改变传入的list
    var newList = new List<T>();
    foreach (var item in list) {
        newList.Insert(Random.Range(0,newList.Count+1), item);
    }
    return newList;
}

&emsp;代码非常简洁，而且思路也很简单，就是对原数组中的每一个元素，依次将其随机插入新数组中，就像是从牌堆里按顺序抓牌，但是随机地插入手上的牌中。
&emsp;由于出现了数组的插入，时间复杂度是O($n^2$)，使用了额外空间以保证不改动原数组，空间复杂度为O(n)。
&emsp;证明似乎相当麻烦，不过我们可以很简单地证明原位置为0和n-1的元素出现在位置0和n-1的概率都是$\frac{1}{n}$。
&emsp;不过我猜这个算法应该也是满足每一个元素出现在每一个位置的概率相等的。

思路参考：https://blog.csdn.net/qq_26399665/article/details/79831490