[数据结构与算法]算法与数据结构-排序函数

对于各种基本数据类型的一维数组的排序，我们通常可以使用Java中自带的sort函数对其进行排序。

public static void main(String[] args) {
	char[] a = {'a','v','d','o'};
	Arrays.sort(a);
    System.out.println(Arrays.toString(a));
}

然而对于自定义数据类型的排序，我们通常要继承Comparable接口，或者Comparator接口，来实现排序。

Comparable接口

Comparable 是排序接口。若一个类实现了Comparable接口，就意味着“该类支持排序”。接口中通过x.compareTo(y)来比较x和y的大小。若返回负数，意味着x比y小；返回零，意味着x等于y；返回正数，意味着x大于y。

继承Comparable接口的类，是需要覆写compareTo函数的。

public class test {
    public static void main(String[] args) {
        Job job1 = new Job(1, 1);
        Job job2 = new Job(2, 1);
        Job[] job = {job1, job2};
        Arrays.sort(job);
        System.out.println(Arrays.toString(job));
    }
}

class Job implements Comparable<Job> {
	int s;
	int t;

	public Job(int s, int t) {
		this.s = s;
		this.t = t;
	}

	@Override
	public int compareTo(Job other) {
		int x = this.t - other.t;
		if (x == 0) {
			return this.s - other.s;
		}else {
			return x;
		}
	}
}

对于上面的程序，如果我们需要对一个Job类型数组进行排序，就可以使用函数Arrays.sort(Object[] object)实现。

注意：

• Comparable接口是实现对自定义类型数组的排序。

Comparator接口

Comparator 是比较器接口。我们可以通过“实现Comparator类来新建一个比较器”，然后通过该比较器对类进行排序。若返回负数，意味着x比y小；返回零，意味着x等于y；返回正数，意味着x大于y。

继承Comparator接口是需要实现compare函数的。

private static class edge {
	public int a;// 起点
	public int b;// 终点
	public int value;// 权值

	public edge(int a, int b, int value) {
		this.a = a;
		this.b = b;
		this.value = value;
	}
}

private static class MyComparator implements Comparator<edge> {
	public int compare(edge o1, edge o2) {
		if (o1.value > o2.value)
			return 1;
		else if (o1.value < o2.value)
			return -1;
		return 0;
	}
}

对于上面的程序，如果我们需要对一个list集合进行排序，我们通常可以使用函数Collections.sort(List list, new MyComparator());

当然对于上面的程序，我们也可以改成用一个匿名内部类的形式来表达。

// 该匿名内部类可以写在一个函数内，直接替代MyComparator类和排序函数
Collections.sort(list, new Comparator<edge>() {
	public int compare(edge o1, edge o2) {
		return o1.value - o2.value;
	}
});

注意：

• Comparator接口是对自定义类型的集合进行排序

• Comparator接口的实现是在类的外部(意思就是在自定义类的外部，再创建一个类。除非使用匿名内部类)。