Collections.sort(List list) list排序學習筆記

先上代碼：

class ListSortExample {

private String flag ;

public ListSortExample(String flag){

this.flag = flag;

}

public String getFlag(){

return this.flag;

}

public void setFlag(String flag){

this.flag = flag;

}

}

/**

* 比較器，重寫compare方法，根據ListSortExample的flag字段來排序ListSortExample

*

*/

class ComparatorListSort implements Comparator{

public int compare(Object arg0, Object arg1) {

ListSortExample example0=(ListSortExample)arg0;

ListSortExample example1=(ListSortExample)arg1;

//首先比較年齡，如果年齡相同，則比較名字

int flag=example0.getFlag().compareTo(example1.getFlag());

return flag;

}

}

public class TestListSort{

public static void main(String[] args){

List<ListSortExample> sortExampleList=new ArrayList<ListSortExample>();

sortExampleList.add(new ListSortExample("aa"));

sortExampleList.add(new ListSortExample("ee"));

sortExampleList.add(new ListSortExample("bb"));

sortExampleList.add(new ListSortExample("cg"));

Comparator comparator=new ComparatorListSort();

//排序--注意：sortExampleList中的對象引用必須被comparator進行比較了，即是：comparator對象的compare方法一定是對sortExampleList中的對象就行比較

Collections.sort(sortExampleList, comparator);

for (ListSortExample example:sortExampleList){

System.out.println(example.getFlag());

}

}

} 

運作結果：

aa

bb

cg

ee

上面初步對Collections.sort的應用做了一個簡單的描述。

下面的篇章我們将會Collections.sort實作進行解析：見代碼和代碼注釋

public static <T> void sort(List<T> list, Comparator<? super T> c) {

//将排序list轉化為數組

Object[] a = list.toArray();

//然後調用Arrays的靜态方法sort()進行排序，是以說Collections的sort()功能是委派Arrays來實作的，我們重點看看Arrays的sort()方法

Arrays.sort(a, (Comparator)c);

//這邊簡單：将排序完成的數組對象中的資料指派給list對象

ListIterator i = list.listIterator();

for (int j=0; j<a.length; j++) {

i.next();

i.set(a[j]);

}

}

public static <T> void sort(T[] a, Comparator<? super T> c) {

//數組拷貝

T[] aux = (T[])a.clone();

if (c==null)

//如果比較器為空，采用預設比較器

mergeSort(aux, a, 0, a.length, 0);

else

//采用使用者自定義的比較器來比較排序

mergeSort(aux, a, 0, a.length, 0, c);

}

private static void mergeSort(Object[] src,

Object[] dest,

int low, int high, int off,

Comparator c) {

int length = high - low;

//當數組的資料小于或者等于7個時候，直接采用冒泡排序法進行比較，然後傳回

// Insertion sort on smallest arrays

if (length < INSERTIONSORT_THRESHOLD) {

for (int i=low; i<high; i++)

for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)

swap(dest, j, j-1);

return;

}

// Recursively sort halves of dest into src

int destLow = low;

int destHigh = high;

low += off;

high += off;

int mid = (low + high) >>> 1;

//如果數組中的個數大于7的話，通過調用遞歸方法，一直将原數組劃分成多個小數組，數組的長度在7之間的，将這些小數組的中的資料按比較器中的規則排好序

//通過A,B将數組一分為二的，然後再将1/2的數組再次劃分為2個，直至最後被劃分的數組的長度在7之内，

mergeSort(dest, src, low, mid, -off, c);----A //對src[low], src[mid](假如程為數組1)之間的資料進行排序

mergeSort(dest, src, mid, high, -off, c);----B//對src[mid], src[high](假如程為數組2)之間的數組進行排序

//下面的操作就是将内部已經排序好的數組1，2就行排序

// If list is already sorted, just copy from src to dest. This is an

// optimization that results in faster sorts for nearly ordered lists.

//當數組2的第一個資料(也就是最小資料)大于數組1的最後一個資料(就是最大資料)，直接合并倆數組到到目标數組

if (c.compare(src[mid-1], src[mid]) <= 0) {

System.arraycopy(src, low, dest, destLow, length);

return;

}

// Merge sorted halves (now in src) into dest

//否則采用算法，什麼算法我也忘了，很簡單的，依次比較，将比較好了的資料指派給目标數組

for(int i = destLow, p = low, q = mid; i < destHigh; i++) {

if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)

dest[i] = src[p++];

else

dest[i] = src[q++];

}

} 

廢話再說倆句，竟然要排序，顯然就要比較要排序元素的順序或者大小，而比較器的作用就是用來幹這個的。用比較器來實作對排序元素的比較。例如上面的代碼：Collections.sort(sortExampleList, comparator)；comparator比較器中的compare()方法就是用來比較sortExampleList中的ListSortExample對象。