设A的n个元素都不相同，证明下述算法产生的排列A[1]，A[2]，…，A[n]服从均匀分布： Random Permute Array（A) /

设A的n个元素都不相同，证明下述算法产生的排列A[1]，A[2]，…，A[n]服从均匀分布：

Random Permute Array(A) //数组A[1..n]

1．for i←1 to n do

2．产生{i，i+1，…，n}上的均匀随机数k

3．交换A[i]与A[k]

这段程序能起到随机化输入，使其服从均匀分布的作用．比如，在快速排序算法的前面加上这段程序，就得到随机快速排序算法．