Sort源码实现比较Go&Java语言风格(2)
接上篇博文，工作中用到了go排序的功能，作为go新手，在参照着例子，并读了go的sort.go部分涉及的源码，了解了go中排序的细节和实现算法，这些在上篇博文中有介绍。作为一个java ZHONGDU*2的用户，不由自主的想到了java中对应实现的样子，在这里也非常简要的贴出来，描述下java中排序的用法，和java源码中对应部分的实现，比较好奇java是和go一样，也用的时候快速排序吗？
3 Java 排序源码解析
主要代码Looks like this：
3.1 使用例子
1public class Person implements Comparable<Person> {
2private String name;
3private int age;
4
5
6@Override
7public int compareTo(Person o) {
8return this.age - o.age;
9}
10
11public static void main(String args[])
12{
13List<Person> persons = new ArrayList<Person>();
14Collections.sort(persons);
15}
16}
和go中不同，必须要在class的第一行implements Comparable这个接口，然后在实现这个接口中定义的compareTo方法，告诉接口到底元素是怎么比较大小的。于是这也追踪下Collections.sort()方法中是如何使用这个compareTo规则来进行排序的。
3.2 源码解析
Collections是一个工具类，调用的是另外一个工具类Arrays中提供的静态方法。java中很少有class名用复数的，和Collection这也一个单数表达的是interface不同，这两个有悠久历史的类下面提供了很多static的工具方法。
1public static <T extends Comparable<? super T>> void sort(List<T> list) {
2Object[] a = list.toArray();
3Arrays.sort(a);
4ListIterator<T> i = list.listIterator();
5for (int j=0; j<a.length; j++) {
6i.next();
7i.set((T)a[j]);
8}
9}
看到Arrays中其实调用的是归并排序，clone一个是待排序的数组，排序的结果放在原来的数组上。
1public static void sort(Object[] a) {
2Object[] aux = (Object[])a.clone();
3mergeSort(aux, a, 0, a.length, 0);
4}
再看mergesort的实现，也是看少于一个阈值INSERTIONSORT_THRESHOLD = 7则直接进行插入排序（为什么和go一样阈值都是7！）。否则就是递归的分而治之的的从中间把待排序的数据二分成两部分，对每部分进行归并排序，直到一部分里面数据时有序为止。然后对有序的子集进行merge，最终达到大的集合整体有序。是我们想象中的归并排序 。
1/**
2* Src is the source array that starts at index 0
3* Dest is the (possibly larger) array destination with a possible offset
4* low is the index in dest to start sorting
5* high is the end index in dest to end sorting
6* off is the offset to generate corresponding low, high in src
7*/
8private static void mergeSort(Object[] src,
9Object[] dest,
10int low,
11int high,
12int off) {
13int length = high - low;
14
15
16// Insertion sort on smallest arrays
17if (length < INSERTIONSORT_THRESHOLD) {
18for (int i=low; i<high; i++)
19for (int j=i; j>low &&
20((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
21swap(dest, j, j-1);
22return;
23}
24
25// Recursively sort halves of dest into src
26int destLow = low;
27int destHigh = high;
28low += off;
29high += off;
30int mid = (low + high) >>> 1;
31mergeSort(dest, src, low, mid, -off);
32mergeSort(dest, src, mid, high, -off);
33
34// If list is already sorted, just copy from src to dest. This is an
35// optimization that results in faster sorts for nearly ordered lists.
36if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
37System.arraycopy(src, low, dest, destLow, length);
38return;
39}
40
41// Merge sorted halves (now in src) into dest
42for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
43if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
44dest[i] = src[p++];
45else
46dest[i] = src[q++];
47}
48}
交互两个元素位置的方法不出所料长得是这个样子。
1/**
2* Swaps x[a] with x[b].
3*/
4private static void swap(Object[] x, int a, int b) {
5Object t = x[a];
6x[a] = x[b];
7x[b] = t;
8}
看两者的源码实现，第一印象，从使用的排序算法看，两者都采用了总体时间复杂度较好的算法，复杂度一般都是n*logn。go使用的是快排 ，尽管不是一个典型快排，用的是快排的思路。java使用的是归并排序 。算法决定了go中的排序不是staable，而java中采用的是stable的 。