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接口。