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

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

3.2 源码解析

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

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

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

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

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

但明显算法不是咱这个语言初学者关注的重点,重点还是通过这个例子和其涉及到的源码中的实现对两种语言语法的理解,通过源码来学习一门新语言是一个老程序员比较喜欢的途径。下一部分尝试详细比较下两者在使用、排序源码和语言上的不同。最主要是,作为初学者对go的感受和理解。

原创文章。为了维护文章的版本一致、最新、可追溯,转载请注明: 转载自idouba

本文链接地址: Sort源码实现比较Go&Java语言风格(2)


, ,

Trackbacks/Pingbacks

  1. Sort源码实现比较Go&Java语言风格(1) | idouba - 2016年4月21日

    […] 至此,结合这个例子,和一点源码理解了go中排序的使用方法。写自己的代码让待排序的集合实现以上三个方法Len、Less、Swap,调用sort.go的Sort方法,完成排序功能,顺利完成手里的feature开发。 故事到这里本该结束了,非常不受控制的,脑子里半秒钟就闪过这个例子在java中的样子,于是就有了后面的故事。。。 […]

发表评论