Just for fun for 随机排列算法的一个证明

对n个元素的数组，一个极简单有效的随机排列算法如下所示：
for(int i = n-1; i > 0; i–){
swap(i,rand()%(i+1));
}
这个算法初看起来并不自然，但其实是很简单的。直观地看，排列过程中，数组分为两部分：排列就绪部分（长度为n-i）和候选元素部分(长度为i)。每次从候选元素部分随机取一元素(rand()%(i+1))，放到排列就绪部分头部，将所占据位置上原来的元素扔进候选元素部分。注意到，候选元素部分的顺序是无关紧要的，因为一个元素无论处于什么位置，下一次被选到的概率都是1/候选部分长度。因此为了算法复杂度低和简单起见，每次都将被占据位置的元素与被选到的元素交换（这两者有可能是同一元素）。简单地说，它的思想就是从一堆元素中随机选出一个来，再从剩下的元素里随机选择，直到选完为止。
严格证明的话，用数学归纳法是简单的，对n进行归纳即可。但好久不做数学题，头脑快生锈了，因此尝试一下复杂一些的证明，证明思想是对原位置i的元素进行跟踪。