线性时间复杂的洗牌算法

昨天在wiki上看到的线性时间复杂度的算法，把他用代码实现出来了
函数里的shuffle_func2
具体参见这里http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
以下代码帖到你的编译器里，可以看到两种算法明显的效率之差了。

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
using namespace std;
int *a=0;
bool * fetch_flag=0;
vector<int>result_set;

void init_arr()
{
    delete[]a;
    delete[]fetch_flag;
    a = new int[100000];
    fetch_flag = new bool[100000];
    result_set.clear();
    for(int i=0; i<100000; i++)
    {
        a[i]=i+1;
        fetch_flag[i]=false;
    }
}
void shuffle_func1()
{
    int pos,counter,real_pos;
    srand(time(NULL));
    for(int i=100000; i>0; i--)
    {
        pos = rand()%i+1;
        //cout<<pos<<endl;
        counter=0;

        for(int j=0; j<100000,counter!=pos; j++)
        {
            if(fetch_flag[j]==false){
                counter++;
            }
            real_pos=j;
        }
        result_set.push_back(a[real_pos]);
        fetch_flag[real_pos]=true;
    }
}
void shuffle_func2()
{
    srand(time(NULL));
    for(int i=100000;i>0;i--){
        int pos = rand()%i;
        result_set.push_back(a[pos]);
        swap(a[pos],a[i-1]);
    }
}
int main()
{

    init_arr();
    clock_t t_start = clock();
    shuffle_func1();
    clock_t t_end = clock();
    cout<<"time 1"<<t_end-t_start<<endl;



    init_arr();
    t_start = clock();
    shuffle_func2();
    t_end = clock();
    cout<<"time 2"<<t_end-t_start<<endl;



    return 0;
}