总体评述
关于使用概率算法的正确性，我的个人方法是：如果你知道如何证明它是正确的，那么它可能是正确的；如果你不知道，那么它肯定是错误的。
换句话说，试图分析每一个可能出现的算法通常是无望的：你必须不断寻找一种算法，直到你找到一种你能够证明其正确性的算法。
通过计算分布来分析随机算法
我知道一种比简单的“进行大量测试并检查均匀性”更强的“自动”分析洗牌（或更普遍地说，随机使用算法）的方法。你可以机械地计算与算法的每个输入相关联的分布。
一般的想法是，随机使用算法探索了可能性的一部分。每次你的算法在集合中（例如{true, false}代表抛硬币）请求一个随机元素时，你的算法有两种可能的结果之一，并且其中一个被选择。你可以改变你的算法，使其不返回可能的结果之一，而是同时探索所有解决方案，并返回所有可能的结果和相关的分布。
一般来说，这需要深入重写你的算法。如果你的语言支持分界限定，那么你不必这样做；你可以在请求一个随机元素的函数内部实现“探索所有可能结果”的功能（想法是随机生成器不返回结果，而是捕获与你的程序相关联的继续运行，并以所有不同的结果运行它）。有关此方法的示例，请参见oleg's HANSEI。
一种中介且可能不那么深奥的解决方案是将这个“可能结果的世界”表示为一个单子，使用像Haskell这样具有单子编程功能的语言。以下是使用probability包的概率单子在Haskell中实现您算法变体¹的示例：
import Numeric.Probability.Distribution
shuffleM :: (Num prob, Fractional prob) => [a] -> T prob [a]
shuffleM [] = return []
shuffleM [x] = return [x]
shuffleM (pivot:li) = do
(left, right) <- partition li
sleft <- shuffleM left
sright <- shuffleM right
return (sleft ++ [pivot] ++ sright)
where partition [] = return ([], [])
partition (x:xs) = do
(left, right) <- partition xs
uniform [(x:left, right), (left, x:right)]
你可以针对给定的输入运行它，并获得输出分布：
*Main> shuffleM [1,2]
fromFreqs [([1,2],0.5),([2,1],0.5)]
*Main> shuffleM [1,2,3]
fromFreqs
[([2,1,3],0.25),([3,1,2],0.25),([1,2,3],0.125),
([1,3,2],0.125),([2,3,1],0.125),([3,2,1],0.125)]
你可以看到，这个算法在输入大小为2时是均匀的，但在输入大小为3时是不均匀的。
与基于测试的方法的区别在于，我们可以在有限步骤内获得绝对确定性：它可能相当大，因为它涉及到对可能性世界的详尽探索（但通常小于2^N，因为有类似结果的分解），但如果返回一个非均匀分布，我们就确定该算法是错误的。当然，如果它对于
[1..N]和
1 <= N <= 100返回了均匀分布，那么你只知道你的算法在长度为100的列表上是均匀的；它仍然可能是错误的。
¹：这个算法是你的Erlang实现的变体，因为它处理了特定的枢轴。如果我像你一样不使用枢轴，那么输入大小就不再每次缩小了：算法还考虑了所有输入都在左侧列表（或右侧列表）的情况，并陷入了无限循环。这是概率单子实现的弱点（如果算法具有非终止的概率0，则分布计算仍可能发散），我还不知道如何解决。
基于排序的洗牌
这里是一个简单的算法，我相信我可以证明它的正确性：
1. 为你的集合中的每个元素选择一个随机键。
2. 如果这些键不全都不同，则从步骤1重新开始。
3. 根据这些随机键对集合进行排序。
如果你知道碰撞(两个随机选择的数字相等)的概率足够低，可以省略步骤2，但如果没有它，洗牌不是完全均匀的。如果您在[1..N]中选择键，其中N是您的集合的长度，将会有很多碰撞(
生日问题)。如果您选择32位整数作为密钥，在实践中冲突的概率很低，但仍然受到生日问题的影响。如果您使用无限(惰性评估)比特串作为密钥，而不是有限长度的密钥，则碰撞的概率变为0，不再需要检查是否不同。这是一个OCaml中的洗牌实现，使用惰性实数作为无限比特串:
type 'a stream = Cons of 'a * 'a stream lazy_t
let rec real_number () =
Cons (Random.bool (), lazy (real_number ()))
let rec compare_real a b = match a, b with
| Cons (true, _), Cons (false, _) -> 1
| Cons (false, _), Cons (true, _) -> -1
| Cons (_, lazy a'), Cons (_, lazy b') ->
compare_real a' b'
let shuffle list =
List.map snd
(List.sort (fun (ra, _) (rb, _) -> compare_real ra rb)
(List.map (fun x -> real_number (), x) list))
还有其他的"纯洗牌"方法。一种不错的方法是apfelmus的基于归并排序的解决方案。
算法考虑：先前算法的复杂度取决于所有键都不同的概率。如果将它们选为32位整数，那么特定键与另一个键发生冲突的概率就是4十亿分之一。按这些键排序是O(n log n)，假设随机选择一个数字是O(1)。
如果你有无限的比特串，你永远不需要重新开始选择，但复杂度与“平均评估流元素的数量”有关。我猜平均值是O(log n)（因此总共仍然是O(n log n)），但没有证明。
...而且我认为你的算法可行
经过更多的思考，我认为（像douplep一样），你的实现是正确的。以下是一个非正式的解释。
列表中的每个元素都会被多个random:uniform() < 0.5测试所测试。对于一个元素，你可以将那些测试的结果作为一个布尔值或{0, 1}的列表与之关联。在算法开始时，你不知道任何数字关联的列表。在第一次partition调用之后，你知道每个列表的第一个元素，等等。当你的算法返回时，测试列表完全已知，元素按照这些列表进行排序（按字典顺序排序，或者被视为实数的二进制表示）。
因此，您的算法相当于按无限位字符串键进行排序。分割列表的操作，类似于快速排序对枢轴元素的分割，实际上是一种根据二进制位中给定位置，将估值为0和估值为1的元素分开的方法。
由于位字符串都不同，因此排序是均匀的。事实上，两个具有相等实数值的元素在第n位上相等，在递归shuffle调用的深度n期间发生的分区的同一侧。该算法仅在所有分区结果为空或单件时终止：所有元素都已通过至少一个测试分离，并且具有一个不同的二进制小数。
概率终止
关于您的算法（或我的等效基于排序的方法）的一个微妙点是，终止条件是概率性的。Fisher-Yates始终在已知步数（数组中的元素数）之后终止。使用您的算法，终止取决于随机数生成器的输出。
可能会出现使您的算法发散而不是终止的输出。例如，如果随机数生成器总是输出0，则每个partition调用都将返回未更改的输入列表，在其中递归调用shuffle：您将无限循环。
然而，如果您确信您的随机数生成器是公平的，即不作弊并始终返回独立均匀分布的结果，则这不是问题。在这种情况下，测试
random:uniform() < 0.5始终返回
true（或
false）的概率恰好为0：
- 前N次调用返回
true的概率为2^{-N}
- 所有调用都返回
true的概率是无限交集的概率，对于所有N，第一次N次调用返回0的事件，它是2^{-N}的下确界极限¹，即0
¹：有关数学细节，请参见http://en.wikipedia.org/wiki/Measure_(mathematics)#Measures_of_infinite_intersections_of_measurable_sets
更一般地，仅当一些元素与相同的布尔流相关联时，算法才不会终止。这意味着至少有两个元素具有相同的布尔流。但是，两个随机布尔流相等的概率也是0：位置K上的数字相等的概率为1/2，因此前N个数字相等的概率为2^{-N}，同样的分析适用。
因此，您知道您的算法具有概率1终止。这是比Fisher-Yates算法略弱的保证，后者总是终止。特别是，您容易受到恶意对手攻击的攻击，该对手可以控制您的随机数生成器。
使用更多的概率论，您也可以计算给定输入长度的算法运行时间分布。这超出了我的技术能力，但我认为这很好：我假设您只需要平均查看O(log N)个数字，就可以检查所有N个惰性流是否不同，并且更高运行时间的概率呈指数递减。
lists:split``lists:droplast和lists:append不会使实施标准算法变得微不足道吗？ - user645280