这章讲随机化的思想在算法里面的运用，讲理论的内容要多一点，核心的算法就俩，而且做的还是同一件事：将一个数组里面的数据进行一次随机排列。
讲了两种方法，一种是产生一个随机数组（里面的每一个值都是0~len*len*len之间的一个随机数），然后将此数组作为key，对原来的数组进行一次“排序”，排序之后，就得到原来数组的一个随机排列。Java代码如下：
public void permuteBySorting(int[] data) { // TODO Auto-generated method stub int n = data.length; int p[] = new int[n]; Random rand = new Random(); //给每一个p[i]赋一个随机值 for(int i=0; i<n; i++) { p[i] = rand.nextInt(n*n*n); //产生一个0~(n*n*n-1)之间的随机整数 } sort(data, p); //data[i]以p中对应的p[i]为key，对data进行排序 }
这种方法真正的cost在于sort(data, p)部分的cost
第二种方法就巧妙多了，效率也高多了，可以在原地、O(n)时间内完成。它的思想是：
对于每一个 i from 0 to len-1，将data[i]与在｛data[i]、data[i+1]、…、data[len-1]｝当中随机取一个值进行交换。这样一次循环下来，data数组就完成了一次随机排列。稍微想想，就会发现这个思想还真是正确的，当然，书上进行了严谨的数学证明。
Java代码如下：
public void randomizeInPlace(int[] data) { // TODO Auto-generated method stub Random rand = new Random(); int len = data.length; int temp, tempIndex; for(int i=0; i<len-1; i++) { //产生一个从i到len-1之间的随机整数，包括i，也包括len-1，赋给tempIndex; tempIndex = rand.nextInt(len-1-i)+i; //将data[i]与data[tempIndex]进行交换 temp = data[i]; data[i] = data[tempIndex]; data[tempIndex] = temp; } }
除了这两个算法，书上还提到一个Hiring Problem，这个问题还是比较有趣的。另外还有一个概念：
uniform random permutation: every permutation of the numbers 1 through n is equally likely to be produced.
