源于算法导论中文第三版第100页关于快速排序的随机化版本。
也就是在算法中引入随机性。 使得算法对于所有的输入都有一个好的期望性能。 这里采用的办法是对于任何一种给定的输入， 我们采用一种 随机抽样（random sampling）的 技术, 对这个给定的输入进行重新排列。 使得我们等可能的获得者写数字的任意排列。
一个比较naive的办法就是创建一个辅助数组temp[]，将数组arr[]内的元素复制到， 然后随机选择temp数组的index, 然后temp[index]复制到数组arr[0]中去。
删除temp[index]数组， 重复这个过程n次， 即可。 该算法的时间复杂度为O（n^2）( yi)
这个技术被称为Fisher-Yates shuffle algorithms， 时间复杂度是O（n）。 我们假设随机数发生器rand()能够在O（1）时间内产生一个随机数。
算法核心思想如下：
(1)选定数组的最后一个元素， 从整个数组中随机选择出一个元素（包含最后一个， 如果是最后一个的话， 相当于自己给自己交换）。
（2）考虑数组0……, n-2(数组的size减少1)， 然后重复步骤（1）, 直至we hit the first element。
伪代码如下：
To shuffle an array a of n elements (indices 0..n-1): for i from n – 1 downto 1 doj = random integer with 0 <= j <= iexchange a[j] and a[i]
分析： 算法施加复杂度为O（n）。
ith 元素到达交换到second last position 的概率是 1/n， 分析见如下：
case1 : i = n -1 , P(last element go to the second last) = P(last element doesnot stay at its original position) x P(the index picked in previous step is picked again) =( (n – 1) /n ) x (1 / (n – 1)) = 1 / n
case 2: 0 < i < n-1 (index of non-last): P(i th element going to the second last position) = P(ith element not picked in the previous) x P(i the element is picked in this step) = (n -1) / n x 1/(n-1) = 1/n
然后generalize 即可。
程序如下：
#include <iostream>#include <cstdlib>#include <ctime>using namespace std;// swapvoid swap(int *a, int*b) {int temp = *a;*a = *b;*b = temp;}/*void swap(int& a, int& b) {// okayint temp = a;a = b;b = temp;// error code// a ^= b;// b ^= a;// a ^= b;}*/// printvoid printArray(int arr[], int n) {for(int i = 0; i < n; ++i) {cout << arr[i] << " ";}cout << endl;}void randomize(int arr[], int n) {srand(time(NULL));for(int i = n -1; i > 0; –i) {int j = rand() % (i + 1);//swap(&arr[i], &arr[j]);swap(arr[i], arr[j]);}}// driver programint main() {int arr[] = {1, 2, 3, 4, 5};int n = sizeof(arr) / sizeof(arr[0]);randomize(arr, n);printArray(arr, n);return 0;}运行的一个结果如下（多次运行， 每次的结果都不一样， 源于随机抽取）：
慎用XOR实现的swap, 有意思！！！
源于自己的这一次观察。 在交换元素的时候， 可以说swap的实现方式有很多种， 例如：
void swap(int *a, int*b) {int temp = *a;*a = *b;*b = temp;}也可以这样：
void swap(int& a, int& b) {// okayint temp = a;a = b;b = temp;}也可以这样（不好，c 容易发生溢出）：
void swap(int& a, int& b) {int c = a + b;a = c – a;b = c – b;}这样？？更不好了, 为了节省几个Bytes的内存值得吗？？？？， 显示出自己高大上？ 自己智商高？ 殊不知聪明反被聪明误！！
void swap(int& a, int& b) {// error codea ^= b;b ^= a;a ^= b;}事实上， 上述代码的速度并没有我们直接声明临时变量由来swap交换好。 设想如果a, b的地址一样的话， 也即swap(a, a)就出现如下错误，就会zero out your value。 在随机化quick sort的时候， 或者上述的 shuffle array， 都会使得我们的值变成了0..
当然， 如果你非要实现这个版本， 最好需要检查一些a， b 的地址是否相同，，也就是说是否指向同一个地址。
if (&a == &b) // added this check to ensure the same address is not passed inreturn;或者如下检测：
if (a == b) // check that values are differentreturn;
done!!!
与一个赏心悦目的人错肩，真真实实的活着，也就够了。
