爱豆吧!

idouba@beta.

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 使用例子

public class Person implements Comparable<Person> {
private String name;
private int age;


@Override
public int compareTo(Person o) {
return this.age - o.age;
}

public static void main(String args[])
{
List<Person> persons = new ArrayList<Person>();
Collections.sort(persons);
}
}

和go中不同,必须要在class的第一行implements Comparable这个接口,然后在实现这个接口中定义的compareTo方法,告诉接口到底元素是怎么比较大小的。于是这也追踪下Collections.sort()方法中是如何使用这个compareTo规则来进行排序的。

3.2 源码解析

Collections是一个工具类,调用的是另外一个工具类Arrays中提供的静态方法。java中很少有class名用复数的,和Collection这也一个单数表达的是interface不同,这两个有悠久历史的类下面提供了很多static的工具方法。

public static <T extends Comparable<? super T>> void sort(List<T> list) {
Object[] a = list.toArray();
Arrays.sort(a);
ListIterator<T> i = list.listIterator();
for (int j=0; j<a.length; j++) {
i.next();
i.set((T)a[j]);
}
}

看到Arrays中其实调用的是归并排序,clone一个是待排序的数组,排序的结果放在原来的数组上。

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

再看mergesort的实现,也是看少于一个阈值INSERTIONSORT_THRESHOLD = 7则直接进行插入排序(为什么和go一样阈值都是7!)。否则就是递归的分而治之的的从中间把待排序的数据二分成两部分,对每部分进行归并排序,直到一部分里面数据时有序为止。然后对有序的子集进行merge,最终达到大的集合整体有序。是我们想象中的归并排序

/**
* Src is the source array that starts at index 0
* Dest is the (possibly larger) array destination with a possible offset
* low is the index in dest to start sorting
* high is the end index in dest to end sorting
* off is the offset to generate corresponding low, high in src
*/
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++];
}
}

交互两个元素位置的方法不出所料长得是这个样子。

/**
* 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;
}

看两者的源码实现,第一印象,从使用的排序算法看,两者都采用了总体时间复杂度较好的算法,复杂度一般都是n*logn。go使用的是快排 ,尽管不是一个典型快排,用的是快排的思路。java使用的是归并排序 。算法决定了go中的排序不是staable,而java中采用的是stable的