前N个自然数的随机置换问题

前N个自然数的随机置换问题 假设需要生成前N个自然数的一个随机置换。例如，{4,3,1,5,2}和{3,1,4,2,5}就是合法的置换，但{5,4,1,2,1}却不是，因为数1出现两次而数3却没有。这个程序常常用于模拟一些算法。我们假设存在一个随机数生成器RandInt(i,j)，它以相同的概率生成i到j之间的一个整数。下面是三个算法： 1.如下填入从A[0]到A[N-1]的数组A;为了填入A[i]，生成随机数直到它不同于已经生成的A[0]，A[1]，...，A[i-1]时，再将其填入A[i]。

int a[10] = {0};

void getRandom(int a[], int length)
{
   int i;
   for(i = 0; i < length; i++)
   {
      int j = RandInt(0, length);
      while(1)
      {
         int k;
         for(k = 0; k < i; k++)
         {
            if(j == a[k])
               break;
         }
         if(k == i)
         {
            a[i] = j;
            break;
         }
         j = RandInt(0, length);
       }
    }
}

算法复杂度：O(N*N*logN) 2.同算法（1），但是要保存一个附加的数组，称之为Used（用过的）数组。当一个随机数Ran最初被放入数组A的时候，置Used[Ran] = 1。这就是说，当用一个随机数填入A[i]时，可以用一步来测试是否该随机数已经被使用，而不是第一个算法那样（可能）进行i步测试。

   void getRandom2(int a[], int length){  
        int Used[length] = {0};  
        for(int i=0; i
算法复杂度：O(N*logN);

3.填写该数组使得A[i] = i+1。然后：
for(i = 1; i < N; i++)
   Swap(&A[i], &A[RandInt(0, i)]);

void getRandom3(int a[], int length){  
        int i;  
        //初始化1-10  
        for(i=0; i
算法复杂度：O(N)