模版方法模式--java数组排序及Comparable接口用法

1、概述

     Arrays类有一个静态方法sort,利用这个方法我们可以传入我们要排序的数组进去排序，因为我们传入的是一个数组的引用，所以排序完成的结果也通过这个引用的来更改数组。对于整数、字符串排序，jdk提供了默认的实现，如果要对一个对象数组排序，则要自己实现java.util.Comparator接口。

 

java.util.Arrays中代码

public static void sort(Object[] a) {
        Object[] aux = (Object[])a.clone();
        mergeSort(aux, a, 0, a.length, 0);
}

 

private static void mergeSort(Object[] src,
				  Object[] dest,
				  int low,
				  int high,
				  int off) {
	int length = high - low;

	// Insertion sort on smallest arrays
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i=low; i<high; i++)
                for (int j=i; j>low &&
			 ((Comparable) dest[j-1]).compareTo(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;
        mergeSort(dest, src, low, mid, -off);
        mergeSort(dest, src, mid, high, -off);

        // 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 (((Comparable)src[mid-1]).compareTo(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 && ((Comparable)src[p]).compareTo(src[q])<=0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

 

private static void swap(Object[] x, int a, int b) {
	Object t = x[a];
	x[a] = x[b];
	x[b] = t;
    }

 冒泡排序法

 

2、例子（鸭子大小比较）

 

Duck需要实现Comparable

public class Duck implements Comparable {

	String name;

	int weight;

	public Duck(String name, int weight) {
		this.name = name;
		this.weight = weight;
	}

	public String toString() {
		return name + " weights " + weight;
	}

	@Override
	public int compareTo(Object o) {
		Duck otherDuck = (Duck) o;
		if (this.weight < otherDuck.weight)
			return -1;
		else if (this.weight == otherDuck.weight)
			return 0;
		else
			return 1;
	}
}

 

public class DackSortTestDrive {

	public static void main(String[] args) {
		Duck[] ducks = {
				new Duck("Daffy", 8),
				new Duck("Dewey", 2),
				new Duck("Howard", 7),
				new Duck("Louie", 2),
				new Duck("Donald", 10),
				new Duck("Huey", 3)
		};
		
		System.out.println("Before sorting:");
		display(ducks);
		
		Arrays.sort(ducks);
		
		System.out.println("\nAfter sorting:");
		display(ducks);
	}
	
	public static void display(Duck[] ducks){
		for (int i = 0; i < ducks.length; i++) {
			System.out.println(ducks[i]);
		}
	}
}

 结果：

Before sorting:
Daffy weights 8
Dewey weights 2
Howard weights 7
Louie weights 2
Donald weights 10
Huey weights 3

After sorting:
Dewey weights 2
Louie weights 2
Huey weights 3
Howard weights 7
Daffy weights 8
Donald weights 10

 

3、总结

 

Arrays.sort方法控制算法，sort()依赖一个Comparable类提供compareTo()的实现。

 

for(int i=low;i<high;i++){
        ...compareTo()...
        ...swap()...
}