[关闭]
@linux1s1s 2017-01-22T08:59:21.000000Z 字数 5436 阅读 1650

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

  1. List<String> stringList = new ArrayList<String>();
  2. stringList.add("nice");
  3. stringList.add("delicious");
  4. stringList.add("able");
  5. stringList.add("moon");
  6. stringList.add("try");
  7. stringList.add("friend");
  8. Collections.sort(stringList);
  9. for (String str : stringList) {
  10. System.out.println(str);
  11. }

我们追踪Collections.sort(stringList)方法

  1. @SuppressWarnings("unchecked")
  2. public static <T extends Comparable<? super T>> void sort(List<T> list) {
  3. Object[] array = list.toArray();
  4. Arrays.sort(array);
  5. int i = 0;
  6. ListIterator<T> it = list.listIterator();
  7. while (it.hasNext()) {
  8. it.next();
  9. it.set((T) array[i++]);
  10. }
  11. }

然后进入主体Arrays.sort(array)

Array

  1. public static void sort(Object[] array) {
  2. ComparableTimSort.sort(array);
  3. }

继续追踪下去,进入ComparableTimSort

  1. static void sort(Object[] a, int lo, int hi) {
  2. Arrays.checkStartAndEnd(a.length, lo, hi);
  3. int nRemaining = hi - lo;
  4. if (nRemaining < 2)
  5. return; // Arrays of size 0 and 1 are always sorted
  6. // If array is small, do a "mini-TimSort" with no merges
  7. if (nRemaining < MIN_MERGE) {
  8. int initRunLen = countRunAndMakeAscending(a, lo, hi);
  9. binarySort(a, lo, hi, lo + initRunLen);
  10. return;
  11. }
  12. /**
  13. * March over the array once, left to right, finding natural runs,
  14. * extending short natural runs to minRun elements, and merging runs
  15. * to maintain stack invariant.
  16. */
  17. ComparableTimSort ts = new ComparableTimSort(a);
  18. int minRun = minRunLength(nRemaining);
  19. do {
  20. // Identify next run
  21. int runLen = countRunAndMakeAscending(a, lo, hi);
  22. // If run is short, extend to min(minRun, nRemaining)
  23. if (runLen < minRun) {
  24. int force = nRemaining <= minRun ? nRemaining : minRun;
  25. binarySort(a, lo, lo + force, lo + runLen);
  26. runLen = force;
  27. }
  28. // Push run onto pending-run stack, and maybe merge
  29. ts.pushRun(lo, runLen);
  30. ts.mergeCollapse();
  31. // Advance to find next run
  32. lo += runLen;
  33. nRemaining -= runLen;
  34. } while (nRemaining != 0);
  35. // Merge all remaining runs to complete sort
  36. if (DEBUG) assert lo == hi;
  37. ts.mergeForceCollapse();
  38. if (DEBUG) assert ts.stackSize == 1;
  39. }

这个代码片段重点看一下:

  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] 中找到相应位置,并插入。

  2. 开始真正的TimSort过程:

    选取minRun大小,之后待排序数组将被分成以minRun大小为区块的一块块子数组
    a) 如果数组大小为2的N次幂,则返回16(MIN_MERGE / 2)
    b) 其他情况下,逐位向右位移(即除以2),直到找到介于16和32间的一个数

    接下来过程比较复杂,可以参考 DualPivotQuicksort 这个算法。

Comparator

这个接口上面的代码段也有提及,关于这个接口给个Demo直观的看一下:

  1. public class MainTest {
  2. public static void main(String[] args) {
  3. List<User> userList = new ArrayList<User>();
  4. userList.add(new User("Lucy", 19));
  5. userList.add(new User("Jack", 19));
  6. userList.add(new User("Jim", 19));
  7. userList.add(new User("James", 19));
  8. userList.add(new User("Herry", 19));
  9. userList.add(new User("Luccy", 19));
  10. userList.add(new User("James", 18));
  11. userList.add(new User("Herry", 20));
  12. Collections.sort(userList);
  13. for (User user : userList) {
  14. System.out.println(user.getName() + "\t\t" + user.getAge());
  15. }
  16. }
  17. private static class User implements Comparable<User> {
  18. private String name;
  19. private int age;
  20. public User(String name, int age){
  21. this.name = name;
  22. this.age = age;
  23. }
  24. @Override
  25. public int compareTo(User another) {
  26. int compareName = this.name.compareTo(another.getName());
  27. if (compareName == 0) {
  28. return (this.age == another.getAge() ? 0 : (this.age > another.getAge() ? 1 : -1));
  29. }
  30. return compareName;
  31. }
  32. public String getName() {
  33. return name;
  34. }
  35. public int getAge() {
  36. return age;
  37. }
  38. }
  39. }

上面Demo简单的演示了Comparable接口的用法,在使用Collections这个工具类之前,需要告诉这个工具你是如何看待自定义Object的比较的

运行结果:

  1. Herry 19
  2. Herry 20
  3. Jack 19
  4. James 18
  5. James 19
  6. Jim 19
  7. Luccy 19
  8. Lucy 19

当然上面这个Demo也可以这样:运行结果和上面是保持一致的

  1. public class MainTest {
  2. public static void main(String[] args) {
  3. List<User> userList = new ArrayList<User>();
  4. userList.add(new User("Lucy", 19));
  5. userList.add(new User("Jack", 19));
  6. userList.add(new User("Jim", 19));
  7. userList.add(new User("James", 19));
  8. userList.add(new User("Herry", 19));
  9. userList.add(new User("Luccy", 19));
  10. userList.add(new User("James", 18));
  11. userList.add(new User("Herry", 20));
  12. Collections.sort(userList, new Comparator<User>() {
  13. public int compare(User user1, User user2) {
  14. int compareName = user1.getName().compareTo(user2.getName());
  15. if (compareName == 0) {
  16. return (user1.getAge() == user2.getAge() ? 0 : (user1.getAge() > user2.getAge() ? 1 : -1));
  17. }
  18. return compareName;
  19. }
  20. });
  21. for (User user : userList) {
  22. System.out.println(user.getName() + "\t\t" + user.getAge());
  23. }
  24. }
  25. private static class User {
  26. private String name;
  27. private int age;
  28. public User(String name, int age){
  29. this.name = name;
  30. this.age = age;
  31. }
  32. public String getName() {
  33. return name;
  34. }
  35. public int getAge() {
  36. return age;
  37. }
  38. }
  39. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注