@linux1s1s 2017-01-22T16:59:21.000000Z 字数 5436 阅读 2339

Java 排序算法

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

Collections要严格区别于Collection，前者是排序工具类，而后者是Java容器的5大接口其中的一个接口，所以为了很好的区别他们，这里也顺带说一下和这个排序不太相关的容器接口

Java容器接口

以下是Java容器十分重要的5大接口，下面只是给出了最基本的描述

Collection

这是Collections库中所有对象的根类型。Collection表示一组对象，这些对象不一定是有序的，也不一定是可访问的，还可能包含重复对象。在Collection中，可以增加和删除对象，获取其大小并对它执行遍历（iterate）操作

List

List是一种有序的集合。List中的对象和整数从0到length-1一一映射。在List中，可能存在重复元素。List支持Collection的所有操作。此外，在List中，可以通过get方法获取索引对应的对象，反之，也可以通过indexOf方法获取某个对象的索引。还可以用add（index,e）方法改变某个特定索引所对应的元素。List的iterator（迭代器）按序依次返回各个元素。

Map

Map和List类似，其区别在于List把一组整数映射到一组对象中，而Map把一组key对象映射到一组value对象。与其他集合类一样，在Map中，可以增加和删除key-value对（键值对），获取其大小并对它执行遍历操作。Map的具体例子包括：把单词和单词定义的映射，日期和事件的映射，或URL和缓存内容的映射等。

Set

Set是一个无序集合，它不包含重复元素。Set也支持Collection的所有操作。但是，如果在Set中添加的是一个已经存在的元素，则Set的大小并不会改变。

Iterator

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)

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 这个算法。

Comparator

这个接口上面的代码段也有提及，关于这个接口给个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;  
        }  
    }  
}