黑马程序员技术交流社区

标题: 关于shuffle 方法！ [打印本页]
作者: 聂益飞    时间: 2013-1-2 14:45
标题: 关于shuffle 方法！
本帖最后由 niexiaolu 于 2013-1-2 17:23 编辑

最近突然想了解shuffle方法的底层实现方式！进而了解计算机对所谓的“随机”是怎么做的！意思就是计算机是怎么随机获取数，或是角标的！由于手边没有API文档，无法查看shuffle方法的源码！还望各位同学指教指教！！
作者: 刘文超    时间: 2013-1-2 15:07
本帖最后由 刘文超 于 2013-1-2 15:39 编辑

一般计算机的随机数都是“伪随机数”，以一个随机种子作为初始条件，然后用一定的算法不停迭代产生随机数。 随机种子可以是当前的系统时间，又叫真随机数 。
而shuffle只是应用了random而已，比较简单，很好理解：
这个是shuffle的主要思想：
  1. To shuffle an array a of n elements (indices 0..n-1):  
  2.   for i from n − 1 downto 1 do  
  3.        j ← random integer with 0 ≤ j ≤ i  
  4.        exchange a[j] and a[i]
复制代码
就是说逆序遍历一个数组（集合），每一个元素 i 都与 “它之前那些元素（0~ i）中随机的一个元素” 进行互换。
这是JDK源代码：
  1. /**
  2.      * Moves every element of the List to a random new position in the list.
  3.      *  
  4.      * @param list
  5.      *            the List to shuffle
  6.      *  
  7.      * @throws UnsupportedOperationException
  8.      *             when replacing an element in the List is not supported
  9.      */  
  10.     public static void shuffle(List<?> list) {  
  11.         shuffle(list, new Random());  
  12.     }  
  13.   
  14.     /**
  15.      * Moves every element of the List to a random new position in the list
  16.      * using the specified random number generator.
  17.      *  
  18.      * @param list
  19.      *            the List to shuffle
  20.      * @param random
  21.      *            the random number generator
  22.      *  
  23.      * @throws UnsupportedOperationException
  24.      *             when replacing an element in the List is not supported
  25.      */  
  26.     @SuppressWarnings("unchecked")  
  27.     public static void shuffle(List<?> list, Random random) {  
  28.         if (!(list instanceof RandomAccess)) {  
  29.             Object[] array = list.toArray();  
  30.             for (int i = array.length - 1; i > 0; i--) {  
  31.                 int index = random.nextInt(i + 1);  
  32.                 if (index < 0) {  
  33.                     index = -index;  
  34.                 }  
  35.                 Object temp = array[i];  
  36.                 array[i] = array[index];  
  37.                 array[index] = temp;  
  38.             }  
  39.   
  40.             int i = 0;  
  41.             ListIterator<Object> it = (ListIterator<Object>) list  
  42.                     .listIterator();  
  43.             while (it.hasNext()) {  
  44.                 it.next();  
  45.                 it.set(array[i++]);  
  46.             }  
  47.         } else {  
  48.             List<Object> rawList = (List<Object>) list;  
  49.             for (int i = rawList.size() - 1; i > 0; i--) {  
  50.                 int index = random.nextInt(i + 1);  
  51.                 if (index < 0) {  
  52.                     index = -index;  
  53.                 }  
  54.                 rawList.set(index, rawList.set(i, rawList.get(index)));  
  55.             }  
  56.         }  
  57.     }
复制代码
作者: 肖志锋    时间: 2013-1-2 15:19
就是List的下标，以及Random类的nextInt()方法循环遍历，随机交换位置。
作者: 张会文    时间: 2013-1-2 15:54
本帖最后由 张会文 于 2013-1-2 16:07 编辑

计算机做不到真正的随机，所有的计算机随机都是“伪随机”，算法不同而已，绝大部分都是用时间作随机种子
什么是“伪随机数”呢？因为实际上要保证每次生成的随机数都不同，那是不太可能的，我们唯一能做到的只能是尽量使每次生成的数字与前面的不同，并且尽量使生成的数字均匀分布在指定的范围内。
API中的解释：
public static void shuffle（List<?>list）
使用默认随机源对指定列表进行置换。所有置换发生的可能性都是大致相等的。前面描述中使用了不确定的词“大致”，因为随机源只是大致上独立选择位的无偏源。如果它是一个随机选择位的最佳源，那么算法将完全一致的选择置换。此实现向后遍历列表，从最后一个元素一直到第二个元素，将随机选择的元素重复交换到“当前位置”。元素是从列表的一部分随机选择的，该部分列表从第一个元素一直到当前位置（包括）。此方法以线性时间运行。如果指定列表没有实现 RandomAccess 接口并且是一个大型列表，则此实现在改组列表前将指定列表转储到数组中，并将改组后的数组转储回列表中。这避免了二次行为，该行为是原地改组一个“有序访问”列表引起的。
JAVA的Collections类中shuffle的用法 ：
  1. <h2 class="title content-title"> </h2>
  2. <div id="content" class="content mod-cs-content text-content clearfix">
  3. <p>// ShuffleTest.java

  5. import java.util.*;

  7. public class
  8. ShuffleTest {
  9.     public static void main(String[] args) {
  10.         
  11. List<Integer> list = new ArrayList<Integer>();
  12.         for (int i
  13. = 0; i < 10; i++)
  14.             list.add(new Integer(i));
  15.         
  16. System.out.println("打乱前:");
  17.         System.out.println(list);

  19.         
  20. for (int i = 0; i < 5; i++) {
  21.             System.out.println("第" + i +
  22. "次打乱：");
  23.             Collections.shuffle(list);
  24.             
  25. System.out.println(list);
  26.         }
  27.     }
  28. }
  29. </p>
  30. <p></p>
  31. <p></p>
  32. <p></p>
  33. <p></p>
  34. <p>//对,就是将集合中的元素,重新的随机的排序........
  35. import java.util.*;
  36. import
  37. sun.plugin.javascript.navig.Array;

  39. public class Demo {
  40. public Demo()
  41. {
  42. }
  43. public static void main(String[] args) {

  45. ArrayList c=new
  46. ArrayList();

  48. for(int i=0;i <4;i++)
  49. {
  50. c.add(new Integer(i));

  52. }
  53. c.add("西西");
  54. c.add("哈哈");
  55. c.add("呵呵");
  56. c.add("嘿嘿");

  58. Iterator it=c.iterator();
  59. System.out.println("排序前的输出：\n");
  60. for(int
  61. i=0;i <c.size();i++)
  62. {
  63. System.out.println(""+c.get(i));
  64. }


  67. Collections.shuffle(c,new Random());

  69. System.out.println("排序后的输出：\n");
  70. while(it.hasNext())
  71. {

  73. System.out.println(""+it.next());
  74. }

  76. }

  78. }


  81. </p></div><p></p>
复制代码




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2