Comparable与 Comparator，源码分析Collections.sort

1、Comparable

对象实现Comparable<T>接口，对象调用compareTo与另一个对象进行比较。

//jdk1.6接口
public interface Comparable<T> {
   //Compares this object with the specified object for order.
    public int compareTo(T o);
}

//例子
public class Lexeme implements Comparable<Lexeme>{
     /*
     * 词元在排序集合中的比较算法
     * @see java.lang.Comparable#compareTo(java.lang.Object)
     */
	public int compareTo(Lexeme other) {
		//起始位置优先
        if(this.begin < other.getBegin()){
            return -1;
        }else if(this.begin == other.getBegin()){
        	//词元长度优先
        	if(this.length > other.getLength()){
        		return -1;
        	}else if(this.length == other.getLength()){
        		return 0;
        	}else {//this.length < other.getLength()
        		return 1;
        	}
        	
        }else{//this.begin > other.getBegin()
        	return 1;
        }
	}
	
 。。。

}	
//调用
if(this.tail.compareTo(newCell) == 0){ 。。。  }   //>0  <0

 

2、Comparator

list对象排序，Collections.sort调用。  public static <T> void sort(List<T> list, Comparator<? super T> c) 

public interface Comparator<T> {
		// Compares its two arguments for order.
	  int compare(T o1, T o2);
	  boolean equals(Object obj);
}

	/**
	 * 
	 * @Description: hashmap根据值得长度降序排列
	 * 思路：将hashmap转为list，用Collections.sort 配合 比较器对list排序
	 * @author thrillerzw
	 * @create time 2014-4-17
	 */
	static void hashMapSort() {
		Map<String, String> map = new HashMap<String, String>();
		map.put("a", "11");
		map.put("c", "1");
		map.put("b", "111");
		//通过ArrayList构造函数把map.entrySet()转换成list 
		Set<Map.Entry<String, String>> set = map.entrySet();
		List<Map.Entry<String, String>> list = new ArrayList<Map.Entry<String, String>>(set);
		Collections.sort(list, new Comparator<Map.Entry<String, String>>() {
			public int compare(Map.Entry<String, String> o1, Map.Entry<String, String> o2) {
				if (o1.getValue().length() >= o2.getValue().length()) {
					return -1;
				} else {
					return 1;
				}
				//按key排序,字符串compareTo比较  res=0、 res=1 、res=-1;
//				int res=o1.getKey().compareTo(o2.getKey());
//				return res; 
			}
		});
		//排序后，使用排好序的list
		System.out.println(list);
	}

 

3、Collections.sort自定义Comparator源码分析

 public static <T> void sort(List<T> list, Comparator<? super T> c) {
 Object[] a = list.toArray();
 //对数组排序,执行完后：[h=1111111, g=11111, e=11111, b=111, k=111, f=11, a=11, c=1]
 Arrays.sort(a, (Comparator)c);
 ListIterator i = list.listIterator();
 for (int j=0; j<a.length; j++) {
 //修改了lastRet的值，作为set(int index, E element)的index输入
     i.next();
     //位置用lastRet的值
     i.set(a[j]);
 }
}
//	Arrays.sort(a, (Comparator)c);调用
private static void mergeSort(Object[] src,
      Object[] dest,
      int low, int high, int off,
      Comparator c) {
 int length = high - low;
 // Insertion sort on smallest arrays
 //长度小于7，冒泡排序
 if (length < INSERTIONSORT_THRESHOLD) {
     for (int i=low; i<high; i++)
     //调用自定义的compare方法比较。i=1时，1和0比较。i=2时，2和1、1和0比较....
  for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
      //compare结果>0时，交换数组元素
      swap(dest, j, j-1);
     return;
 }
        // Recursively sort halves of dest into src
        int destLow = low;
        int destHigh = high;
        low += off;
        high += off;
        //mid=4
        int mid = (low + high) >>> 1;
        //递归前半部分0--4
        mergeSort(dest, src, low, mid, -off, c);
        ////递归后半部分4--8
        mergeSort(dest, src, mid, high, -off, c);
        // If list is already sorted, just copy from src to dest. This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (c.compare(src[mid-1], src[mid]) <= 0) {
           System.arraycopy(src, low, dest, destLow, length);
           return;
        }
        //src :[g=11111, e=11111, b=111, f=11, h=1111111, k=111, a=11, c=1]的前部分跟后部分比较，结果存入desc
        //dest:[h=1111111, g=11111, e=11111, b=111, k=111, f=11, a=11, c=1]
        // Merge sorted halves (now in src) into dest
        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            //开始p=0 q=4
            if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }
   
   
    /**
     * Swaps x[a] with x[b].
     */
private static void swap(Object[] x, int a, int b) {
 Object t = x[a];
 x[a] = x[b];
 x[b] = t;
}
/*
前后半部分排序长度小于7排序
src
0--4
[f=11, g=11111, e=11111, b=111, c=1, a=11, k=111, h=1111111]
[g=11111,f=11, e=11111, b=111, c=1, a=11, k=111, h=1111111]
[g=11111, e=11111, f=11, b=111, c=1, a=11, k=111, h=1111111]
[g=11111, e=11111, b=111, f=11, c=1, a=11, k=111, h=1111111]
4-8
[g=11111, e=11111, b=111, f=11, h=1111111, k=111, a=11, c=1]
dest
[h=1111111, g=11111, e=11111, b=111, c=1, a=11, k=111, h=1111111]
前后半部分归并后：
src :[g=11111, e=11111, b=111, f=11, h=1111111, k=111, a=11, c=1]
dest:[h=1111111, g=11111, e=11111, b=111, k=111, f=11, a=11, c=1]
*/
//i.next()
 public E next() {
            checkForComodification();
     try {
  E next = get(cursor);
  //修改了lastRet的值
  lastRet = cursor++;
  return next;
     } catch (IndexOutOfBoundsException e) {
  checkForComodification();
  throw new NoSuchElementException();
     }
 }
 
//修改ArrayList指定位置值
public E set(int index, E element) {
 RangeCheck(index);
 E oldValue = (E) elementData[index];
 elementData[index] = element;
 return oldValue;
}