数据结构与算法分析 C++描述（第3版） 习题2.8 详尽分析

for(i = 1; i < n; ++i)
   swap (a[i],a[ randInt(0,i)]);

#include "jtianling/jtianling.h"
#include "boost/dynamic_bitset.hpp"
using namespace std;

//2.8题目中假设存在的随机数生成器
//根据其定义,此算法生成从i到j的随机数,而且包括边界i,j.即i=<n<=j
int randInt(int i, int j)
{
   //确保i<j,不然就交换
   if(i > j)
   {
      int temp = i;
      i = j;
      j = temp;
   }
   //确保范围正确
   return rand()%(j-i+1) + i;
}

//算法,算法描述如题目.8所示,根据习惯,不对arr[]的大小做任何检验
//调用此函数的人应该确保这一点,即arr的大小大于等于n
void RandArrayCreate1(int arr[], int n)
{
   int temp;
   for(int i=0; i<n; ++i)
   {
      while(true)
      {
         temp = randInt(1,n);
         int j = 0;
         while(j<i)
         {
            if(arr[j] == temp){   break;}
            ++j;
         }
         if(j == i)
         {
            arr[j] = temp;
            break;
         }
      }
   }
}

//算法,算法描述如题目.8所示,根据习惯,不对arr[]的大小做任何检验
//调用此函数的人应该确保这一点,即arr的大小大于等于n
void RandArrayCreate2(int arr[], int n)
{
   //为了正好与数值一一对应，浪费位算了,默认就都为flase
   bool *used = new bool[n+1];
   memset(used, 0, sizeof(bool) * (n+1));
   int temp;
   for(int i=0; i<n; ++i)
   {

      while(true)
      {
         temp = randInt(1,n);
         if(used[temp] == false)
         {
            arr[i] = temp;
            used[temp] = true;
            break;
         }
         else
         {
            continue;
         }
      }
   }
   delete []used;

}

//算法,算法描述如题目.8所示,根据习惯,不对arr[]的大小做任何检验
//调用此函数的人应该确保这一点,即arr的大小大于等于n
void RandArrayCreate3(int arr[], int n)
{
   for(int i=0; i<n; ++i)
   {
      arr[i] = i + 1;
   }
   for(int i=0; i<n; ++i)
   {
      swap(arr[i], arr[randInt(0, i)] );
   }
}

void RandArrayCreate2a(int arr[], int n)
{
   //为了正好与数值一一对应，浪费位算了,默认就都为flase
   boost::dynamic_bitset<> used(n+1);
   int temp;
   for(int i=0; i<n; ++i)
   {

      while(true)
      {
         temp = randInt(1,n);
         if(used[temp] == false)
         {
            arr[i] = temp;
            used.set(temp);
            break;
         }
         else
         {
            continue;
         }
      }
   }

}
void RandArrayCreate2b(int arr[], int n)
{
   //为了正好与数值一一对应，浪费位算了,默认就都为flase
   vector<bool> used(n+1);
   int temp;
   for(int i=0; i<n; ++i)
   {

      while(true)
      {
         temp = randInt(1,n);
         if(used[temp] == false)
         {
            arr[i] = temp;
            used[temp] = true;
            break;
         }
         else
         {
            continue;
         }
      }
   }
}

//因为这里主要是比较不同算法的实现,所以这里不区分算法及其实现,都称为算法
//比较算法的函数，其中算法函数的参数为数组（array)和整数(int)
//简写为AI，为了防止混乱，这里我没有使用函数的重载
//准备以后有新的不同参数的算法时再加入新的比较函数
//比较函数的参数解释如下：
//第一参数:各算法的用vector<>表示的函数指针数组
//第二参数:vector<int>表示的一系列算法函数第二参数,用以做算法增长比较
//主要注意的是，这里的第二参数实际也是算法函数第一参数数组的大小
void CompareAlgorithmAI(const std::vector<pfAI> &pfAIVec,const std::vector<int>& vec)
{
   double timeInAll = GetTime();  //这里保存所有比较花费的时间
   std::ofstream out("CompareAlogrithmAIResult.txt");//将结果保存在这里
   
   //在文件中输入第一行
   out <<"parameter" <<'/t';
   for(int i=0; i<pfAIVec.size(); ++i)
   {
      out <<"Algorithm " <<i+1 <<'/t';
   }
   out <<std::endl <<std::setprecision(4) <<std::scientific;
   
   double timeTaken;  //每个算法一次消耗的时间

   //以算法参数的数组个数为循环条件,每个数值让各个算法分别调用
   for(int i=0; i<vec.size(); ++i)
   {
      out <<vec[i] <<'/t';
      int *arr = new int[ vec[i] ];  //每次动态生成一个数组
      for(int j=0; j<pfAIVec.size(); ++j)
      {
       
         timeTaken = GetTime();
         pfAIVec[j](arr, vec[i]); //实际调用不同算法
         timeTaken = GetTime() - timeTaken;
         out <<timeTaken <<'/t';
      }
      delete []arr;   //删除arr,因为只考察算法的效率,所以根本不关心结果
                     //至于各算法是否正确由调用者保证
      out<<std::endl;
   }
   timeInAll = GetTime() - timeInAll;
   out <<"Compared time in all: " <<timeInAll <<std::endl;
}