Java 集合中的排序算法浅析

作者：京东物流 秦彪

1.  引言

排序是一个Java开发者，在日常开发过程中随处可见的开发内容，Java中有丰富的API可以调用使用。在Java语言中，作为集合工具类的排序方法，必定要做到通用、高效、实用这几点特征。使用什么样排序算法会比较合适，能够做到在尽量降低时间、空间复杂度的情况下，又要兼顾保证稳定性，达到优秀的性能。可能从性能角度出发首先会想到的是快速排序，或者归并排序。作为jdk提供的通用排序功能，使用又如此频繁，肯定有独特之处，一起来看学习下期中的奥秘。
文中不会过多的介绍几大基本排序算法的方式、由来和思想，主要精力集中在一块探讨java中排序方法所使用的算法，以及那些是值得我们学习和借鉴的内容。文中如有理解和介绍的错误，一起学习，一起探讨，一起进步。
2.  案例

日常使用最为频繁的排序，莫过于如下代码案例，给定一个现有的序列进行一定规则下的排序，配合java8的stream特性，可以很方便的对一个集合进行排序操作（排序规则只是对排序对象及排序方案的限定，不在本文讨论范围内）。

1. List<Integer> list = Arrays.asList(10, 50, 5, 14, 16, 80);
2. System.out.println(list.stream().sorted().collect(Collectors.toList()));

复制代码

在代码执行的过程中SortedOps.java类中 Arrays.sort(array, 0, offset, comparator); 执行了Array集合类型的sort排序算法。

1. @Override
2. public void end() {
3.     Arrays.sort(array, 0, offset, comparator);
4.     downstream.begin(offset);
5.     if (!cancellationWasRequested) {
6.         for (int i = 0; i < offset; i++)
7.             downstream.accept(array[i]);
8.     }
9.     else {
10.         for (int i = 0; i < offset && !downstream.cancellationRequested(); i++)
11.             downstream.accept(array[i]);
12.     }
13.     downstream.end();
14.     array = null;
15. }

复制代码

如果使用Collections.sort() 方法如下打印 list1 和 list2 结果一样，且调用的都是 Arrays 集合类中的 sort 方法。

1. List<Integer> list1 = Arrays.asList(10, 50, 5, 14, 16, 80);
2. System.out.println(list1.stream().sorted().collect(Collectors.toList()));
4. List<Integer> list2 = Lists.newArrayList();
5. list2.addAll(list1);
6. Collections.sort(list2);
7. System.out.println(list2);
8. // 输出：
9. // [5, 10, 14, 16, 50, 80]
10. // [5, 10, 14, 16, 50, 80]

复制代码

2.  Collections.sort 方法介绍

Collections类中关于sort方法定义如下：
[code]public static