List集合隨機(jī)排序算法分析
先說一下JDK 對List的隨機(jī)排序的實(shí)現(xiàn)：
public static void shuffle(List list, Random rnd) {
??? final int SHUFFLE_THRESHOLD??????? =??? 5; //這應(yīng)當(dāng)是一個(gè)經(jīng)驗(yàn)值吧
??????? 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));??//這一種方法是直接調(diào)用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實(shí)現(xiàn)，就使用迭代器遍歷
??????????? for (int i=0; i<arr.length; i++) {
??????????????? it.next();
??????????????? it.set(arr[i]);
??????????? }
??????? }
??? }
再說一下我自己的笨拙實(shí)現(xiàn)：
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的實(shí)現(xiàn)是ArrayList，在時(shí)間效率上要多循環(huán)一次，但在空間上，我的方法非常差，多生成一個(gè)List集合，如果List很大，就更差了。同時(shí)我的算法如果用于Sequence List上，效率是相當(dāng)?shù)牟睿荒苓m合ArrayList,有很大的局限性。
這是因?yàn)椋?如果集合類是RandomAccess的實(shí)現(xiàn)，則盡量用for(int i = 0; i < size; i++) 來遍歷而不要用Iterator迭代器來遍歷，在效率上要差一些。反過來，如果List是Sequence List，則最好用迭代器來進(jìn)行迭代。
JDK中說的很清楚，在對List特別是Huge size的List的遍歷算法中，要盡量來判斷是屬于RandomAccess(如ArrayList)還是Sequence List (如LinkedList），因?yàn)檫m合RandomAccess List的遍歷算法，用在Sequence List上就差別很大，常用的作法就是：
??? 要作一個(gè)判斷：
??? if (list instance of RandomAccess) {
??????? for(int m = 0; m < list.size(); m++){}
??? }else{
??????? Iterator iter = list.iterator();
??????? while(iter.hasNext()){}
??? }
?? 我的項(xiàng)目中List都是基于ArrayList的，所以基本上很少用迭代器來遍歷，而是用for循環(huán)來遍歷，對于迭代器的作用我當(dāng)然很清楚，但是我覺得有點(diǎn)庸人自擾了。
?? 除非你經(jīng)常用Collection作為你的接口方法中的輸入或輸出的集合參數(shù)類型時(shí)，你也就只能用Iterator。
?? 但我一般在接口方法中，一般用List，所以我就不用迭代器，除非我的List是Linked List實(shí)例。
?? 好的作法是：在供外部調(diào)用的接口方法中，使用Collection作為集合參數(shù)類型，在內(nèi)部實(shí)現(xiàn)當(dāng)中，使用List，而不是一味的使用Collections及Iterator，這樣做無異于作繭自縛。
?? 順便說一下JDK中推薦的是對List集合盡量要實(shí)現(xiàn)RandomAccess接口。