反向执行的Fisher-Yates洗牌算法（Algo C）是否正确？

1. Algo C是不是正确的Fisher-Yates洗牌算法实现？ #

Algo C是完全正确的Fisher-Yates洗牌实现，你通过卡方检验得到的均匀分布结论符合实际情况，可通过数学归纳法直接证明其正确性：

• 当数组长度n=2时，循环仅执行1次，i=1，j等概率取0或1，交换后两种排列的生成概率均为1/2，符合均匀分布要求
• 假设数组长度为k时，Algo C可生成等概率的全排列，当数组长度为k+1时，最后一次循环i=k，j从0_{k范围内等概率取值，原第k位的元素会等概率落到0}k的任意位置，剩余前k个元素通过之前的循环已经是均匀排列，因此整体所有排列的生成概率均为1/(k+1)!，完全符合均匀随机排列的要求

Algo C和常见的Algo A、Algo B仅遍历方向不同，核心逻辑都是保证每一步的随机取值范围严格限制在已处理区间内，避免出现排列概率倾斜的问题。

2. 为什么Algo C几乎没有公开应用场景？ #

主要有三点原因：

• 历史沿用惯性：Fisher和Yates最初提出该算法时采用的就是从后向前遍历的版本，后续Knuth在《计算机程序设计艺术》中收录并推广的也是Algo A的实现，绝大多数语言的标准库（比如Java的Collections.shuffle、Python的random.shuffle）都直接沿用了经过工业界数十年验证的经典实现，没有必要更换逻辑一致但认知度更低的变体
• 普遍认知误区：很多开发者容易把Algo C和常见的错误洗牌实现（即每轮循环的j都从整个数组0~n-1的范围随机取）搞混，后者生成的排列概率并不均匀，因此很多人看到正向遍历的洗牌实现会默认判定为错误实现，不会主动使用
• 无额外优势：Algo C和经典实现的时间复杂度、空间复杂度完全一致，也没有边界处理、运行性能上的额外优势，因此没有推广落地的动力

内容的提问来源于stack exchange，提问作者congyuwang