@linux1s1s
2017-01-22T16:59:21.000000Z
字数 5436
阅读 2364
Java
2015-04
在讨论排序算法之前,先来看一个问题:从根目录查找某个文件,要用非递归的方式 (为神马不用递归方式?),下面给出程序截图:
图片来自博客:http://blog.csdn.net/wangchun8926/article/details/8680219
接下来我们不打算详细的讨论典型的排序算法,比如快速排序、归并排序、堆排序、插入排序、冒泡排序等等,对于这些排序算法已经有很好的博客可以参考了:http://blog.csdn.net/bruce_6/article/details/38728493
那该博文要讨论神马? 我们要讨论Java SDK封装好的排序算法,看看SDK是如何提高排序效率的。
Java SDK 涉及排序的类主要有
Collections
类、Array
类、Comparator
接口,而DualPivotQuicksort
类从Java 1.7开始引入,这个多路快速排序效率自然要比快速排序要高,所以我们一般建议直接用SDK为我们封装好的算法,而不是自己去写算法,除非有特殊的需求。
Collections
要严格区别于Collection
,前者是排序工具类,而后者是Java容器的5大接口其中的一个接口,所以为了很好的区别他们,这里也顺带说一下和这个排序不太相关的容器接口
以下是Java容器十分重要的5大接口,下面只是给出了最基本的描述
这是Collections库中所有对象的根类型。Collection表示一组对象,这些对象不一定是有序的,也不一定是可访问的,还可能包含重复对象。在Collection中,可以增加和删除对象,获取其大小并对它执行遍历(iterate)操作
List是一种有序的集合。List中的对象和整数从0到length-1一一映射。在List中,可能存在重复元素。List支持Collection的所有操作。此外,在List中,可以通过get方法获取索引对应的对象,反之,也可以通过indexOf方法获取某个对象的索引。还可以用add(index,e)方法改变某个特定索引所对应的元素。List的iterator(迭代器)按序依次返回各个元素。
Map和List类似,其区别在于List把一组整数映射到一组对象中,而Map把一组key对象映射到一组value对象。与其他集合类一样,在Map中,可以增加和删除key-value对(键值对),获取其大小并对它执行遍历操作。Map的具体例子包括:把单词和单词定义的映射,日期和事件的映射,或URL和缓存内容的映射等。
Set是一个无序集合,它不包含重复元素。Set也支持Collection的所有操作。但是,如果在Set中添加的是一个已经存在的元素,则Set的大小并不会改变。
Iterator(迭代器)返回集合中的元素,其通过next方法,每次返回一个元素。Iterator是对集合中所有元素进行操作的一种较好的方式。一般不建议使用下面这种方式遍历:
接下来讨论我们的主题,Collections
这里重点讨论这个类中的sort()方法,先看个Demo
List<String> stringList = new ArrayList<String>();
stringList.add("nice");
stringList.add("delicious");
stringList.add("able");
stringList.add("moon");
stringList.add("try");
stringList.add("friend");
Collections.sort(stringList);
for (String str : stringList) {
System.out.println(str);
}
我们追踪Collections.sort(stringList)
方法
@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> void sort(List<T> list) {
Object[] array = list.toArray();
Arrays.sort(array);
int i = 0;
ListIterator<T> it = list.listIterator();
while (it.hasNext()) {
it.next();
it.set((T) array[i++]);
}
}
然后进入主体Arrays.sort(array)
public static void sort(Object[] array) {
ComparableTimSort.sort(array);
}
继续追踪下去,进入ComparableTimSort
类
static void sort(Object[] a, int lo, int hi) {
Arrays.checkStartAndEnd(a.length, lo, hi);
int nRemaining = hi - lo;
if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted
// If array is small, do a "mini-TimSort" with no merges
if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi);
binarySort(a, lo, hi, lo + initRunLen);
return;
}
/**
* March over the array once, left to right, finding natural runs,
* extending short natural runs to minRun elements, and merging runs
* to maintain stack invariant.
*/
ComparableTimSort ts = new ComparableTimSort(a);
int minRun = minRunLength(nRemaining);
do {
// Identify next run
int runLen = countRunAndMakeAscending(a, lo, hi);
// If run is short, extend to min(minRun, nRemaining)
if (runLen < minRun) {
int force = nRemaining <= minRun ? nRemaining : minRun;
binarySort(a, lo, lo + force, lo + runLen);
runLen = force;
}
// Push run onto pending-run stack, and maybe merge
ts.pushRun(lo, runLen);
ts.mergeCollapse();
// Advance to find next run
lo += runLen;
nRemaining -= runLen;
} while (nRemaining != 0);
// Merge all remaining runs to complete sort
if (DEBUG) assert lo == hi;
ts.mergeForceCollapse();
if (DEBUG) assert ts.stackSize == 1;
}
这个代码片段重点看一下:
传入的待排序数组若小于阈值MIN_MERGE(Java实现中为32,Python实现中为64),则调用 binarySort,这是一个不包含合并操作的 mini-TimSort。
a) 从数组开始处找到一组连接升序或严格降序(找到后翻转)的数
b) Binary Sort:使用二分查找的方法将后续的数插入之前的已排序数组,binarySort 对数组 a[lo:hi] 进行排序,并且a[lo:start] 是已经排好序的。算法的思路是对a[start:hi] 中的元素,每次使用binarySearch 为它在 a[lo:start] 中找到相应位置,并插入。
开始真正的TimSort过程:
选取minRun大小,之后待排序数组将被分成以minRun大小为区块的一块块子数组
a) 如果数组大小为2的N次幂,则返回16(MIN_MERGE / 2)
b) 其他情况下,逐位向右位移(即除以2),直到找到介于16和32间的一个数
接下来过程比较复杂,可以参考 DualPivotQuicksort
这个算法。
这个接口上面的代码段也有提及,关于这个接口给个Demo直观的看一下:
public class MainTest {
public static void main(String[] args) {
List<User> userList = new ArrayList<User>();
userList.add(new User("Lucy", 19));
userList.add(new User("Jack", 19));
userList.add(new User("Jim", 19));
userList.add(new User("James", 19));
userList.add(new User("Herry", 19));
userList.add(new User("Luccy", 19));
userList.add(new User("James", 18));
userList.add(new User("Herry", 20));
Collections.sort(userList);
for (User user : userList) {
System.out.println(user.getName() + "\t\t" + user.getAge());
}
}
private static class User implements Comparable<User> {
private String name;
private int age;
public User(String name, int age){
this.name = name;
this.age = age;
}
@Override
public int compareTo(User another) {
int compareName = this.name.compareTo(another.getName());
if (compareName == 0) {
return (this.age == another.getAge() ? 0 : (this.age > another.getAge() ? 1 : -1));
}
return compareName;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
}
}
上面Demo简单的演示了Comparable接口的用法,在使用Collections
这个工具类之前,需要告诉这个工具你是如何看待自定义Object的比较的
运行结果:
Herry 19
Herry 20
Jack 19
James 18
James 19
Jim 19
Luccy 19
Lucy 19
当然上面这个Demo也可以这样:运行结果和上面是保持一致的
public class MainTest {
public static void main(String[] args) {
List<User> userList = new ArrayList<User>();
userList.add(new User("Lucy", 19));
userList.add(new User("Jack", 19));
userList.add(new User("Jim", 19));
userList.add(new User("James", 19));
userList.add(new User("Herry", 19));
userList.add(new User("Luccy", 19));
userList.add(new User("James", 18));
userList.add(new User("Herry", 20));
Collections.sort(userList, new Comparator<User>() {
public int compare(User user1, User user2) {
int compareName = user1.getName().compareTo(user2.getName());
if (compareName == 0) {
return (user1.getAge() == user2.getAge() ? 0 : (user1.getAge() > user2.getAge() ? 1 : -1));
}
return compareName;
}
});
for (User user : userList) {
System.out.println(user.getName() + "\t\t" + user.getAge());
}
}
private static class User {
private String name;
private int age;
public User(String name, int age){
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
}
}