随机算法

简而言之，随机算法就是随机设定输入的排列组合。
与概率分析类似，这种方法可以用这种方法来估算算法的平均情况。
主要适用于那些对分布不了解，或者概率分析起来很复杂的算法

两种生成均匀随机排列的随机化方法

• PERMUTE-BY-SORTING
  随机生成一个排序，然后重新排列，以此生成随机序列

PERMUTE-BY-SORTING(A)
  n = A.length
  let P[1. .n] be a new array
  for i = 1 to n
    P[i] = RANDOM(1, n^^3)
  sort A, using P as sort key

• RANDOMIZE-IN-PLACE
  随机的置换所有的元素，从而得到一个新的随机排列

RANDOM-IN-PLACE(A)
  n = A.length
  for i = 1 to n
    swap A[i] with A[RANDOM(i, n)]

具体证明的步骤参考P70-72