将一个数组的元素顺序打乱

给定一个数组,要求把数组内元素的顺序随机打乱,然后输出,主要是要保证效率。

这个算法其实简单,首先从所有元素中随机选取一个与第一个元素进行交换,然后在第二个之后选择一个元素与第二个交换,直到最后一个元素。这样能确保每个元素在每个位置的概率都是1/n。代码如下:

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <time.h>  
  4.   
  5. // 随机打乱一个数组  
  6. void random(int a[], int n)  
  7. {  
  8.     int index, tmp, i;  
  9.     srand(time(NULL));  
  10.     for (i = 0; i <n; i++)  
  11.     {  
  12.         index = rand() % (n – i) + i;  
  13.         if (index != i)  
  14.         {  
  15.             tmp = a[i];  
  16.             a[i] = a[index];  
  17.             a[index] = tmp;  
  18.         }  
  19.     }  
  20. }  
  21. int main()  
  22. {  
  23.     int a[] = {1, 2, 3, 4, 5};  
  24.     int i;  
  25.     random(a, 5);  
  26.     for (i = 0; i < 5; i++)  
  27.         printf(“%d “, a[i]);  
  28.     printf(“\n”);  
  29.     system(“pause”);  
  30.     return 0;  

 

把一个数组的顺序打乱,很常用的算法,比如洗牌。

下面用Java实现:

  1. import java.util.Random;    
  2.     
  3. public class RandomSort {    
  4.     private Random random = new Random();    
  5.     //数组大小    
  6.     private static final int SIZE = 10;    
  7.     //要重排序的数组    
  8.     private int[] positions = new int[SIZE];    
  9.         
  10.     public RandomSort() {    
  11.         for(int index=0; index<SIZE; index++) {    
  12.             //初始化数组,以下标为元素值    
  13.             positions[index] = index;    
  14.         }    
  15.         //顺序打印出数组的值    
  16.         dwn();    
  17.     }    
  18.         
  19.     //重排序    
  20.     public void changePosition() {    
  21.         for(int index=SIZE-1; index>=0; index–) {    
  22.             //从0到index处之间随机取一个值,跟index处的元素交换    
  23.             exchange(random.nextInt(index+1), index);    
  24.         }    
  25.         dwn();    
  26.     }    
  27.         
  28.     //交换位置    
  29.     private void exchange(int p1, int p2) {    
  30.         int temp = positions[p1];    
  31.         positions[p1] = positions[p2];    
  32.         positions[p2] = temp;    
  33.     }    
  34.         
  35.     //打印数组的值    
  36.     private void dwn() {    
  37.         for(int index=0; index<SIZE; index++) {    
  38.             System.out.print(positions[index]+” “);             
  39.         }    
  40.         System.out.println();    
  41.     }    
  42.     
  43.     public static void main(String[] args) {    
  44.         RandomSort rs = new RandomSort();    
  45.         rs.changePosition();    
  46.         rs.changePosition();    
  47.         rs.changePosition();    
  48.     }    
  49. }   
 

不过由于随机数产生器产生的随机数不太随机,所以排序的结果页有很多相似的地方。换一个好的随机数产生器,会达到更好的效果,就能用于洗牌了。
 
 
 
 
 
 

Leave a Reply

Your email address will not be published.