List集合随机排序算法分析

List集合随机排序算法分析

先说一下JDK 对List的随机排序的实现：

public static void shuffle(List list, Random rnd) {　　　　
??? 　　final int SHUFFLE_THRESHOLD??????? =??? 5;　　//这应当是一个经验值吧

??????? int size = list.size();
　　/** 为什么要判断，后面有论述 */
??????? if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
??????????? for (int i=size; i>1; i--)
??????????????? swap(list, i-1, rnd.nextInt(i));??//这一种方法是直接调用List.set方法，属于RandomAccess中的方法
??????? } else {
??????????? Object arr[] = list.toArray();

??????????? // Shuffle array
??????????? for (int i=size; i>1; i--)
??????????????? swap(arr, i-1, rnd.nextInt(i));

??????????? // Dump array back into list
??????????? ListIterator it = list.listIterator();????? //如果不是Random Access实现，就使用迭代器遍历
??????????? for (int i=0; i<arr.length; i++) {
??????????????? it.next();
??????????????? it.set(arr[i]);
??????????? }
??????? }
??? }

再说一下我自己的笨拙实现：
　　public static List randomSortList(List ls, Random random) {
??????????????? List randomList = new ArrayList();???????????????
??????????????? int size = list.size();
?????????????? while (size > 0) {
????????????????? int randomNum = random.nextInt(size);
????????????????? randomList.add(ls.get(randomNum));
????????????????? ls.remove(randomNum); //这一步，对于RandomAccess的集合来说，是O(1)操作
????????????? ?}
?????????????? return randomList;
???? }
评述：
　　如果List的实现是ArrayList，在时间效率上要多循环一次，但在空间上，我的方法非常差，多生成一个List集合，如果List很大，就更差了。同时我的算法如果用于Sequence List上，效率是相当的差，只能适合ArrayList,有很大的局限性。
　　这是因为： 如果集合类是RandomAccess的实现，则尽量用for(int i = 0; i < size; i++) 来遍历而不要用Iterator迭代器来遍历，在效率上要差一些。反过来，如果List是Sequence List，则最好用迭代器来进行迭代。
　　JDK中说的很清楚，在对List特别是Huge size的List的遍历算法中，要尽量来判断是属于RandomAccess(如ArrayList)还是Sequence List (如LinkedList），因为适合RandomAccess List的遍历算法，用在Sequence List上就差别很大，常用的作法就是：
??? 要作一个判断：
??? if (list instance of RandomAccess) {
??????? for(int m = 0; m < list.size(); m++){}
??? }else{
??????? Iterator iter = list.iterator();
??????? while(iter.hasNext()){}
??? }
?? 我的项目中List都是基于ArrayList的，所以基本上很少用迭代器来遍历，而是用for循环来遍历，对于迭代器的作用我当然很清楚，但是我觉得有点庸人自扰了。
?? 除非你经常用Collection作为你的接口方法中的输入或输出的集合参数类型时，你也就只能用Iterator。
?? 但我一般在接口方法中，一般用List，所以我就不用迭代器，除非我的List是Linked List实例。
?? 好的作法是：在供外部调用的接口方法中，使用Collection作为集合参数类型，在内部实现当中，使用List，而不是一味的使用Collections及Iterator，这样做无异于作茧自缚。
?? 顺便说一下JDK中推荐的是对List集合尽量要实现RandomAccess接口。