一. 面试题及剖析

1. 今日面试题

如何对List集合进行排序？

利用Lambda表达式如何对List集合进行排序？

2. 题目剖析

这道题目考察的知识点还是与List集合相关，但其难度与之前的集合内容相比，已经大大降低了。这里其实主要是考察我们对List集合用法、基本特性的实际应用，并且在考察List时顺道考察了我们对排序的掌握情况。整体来看，这道题目偏重于考察我们的代码实操能力，难度不大。

因为集合排序的面试题内容较多，本文会分为两篇文章进行介绍，接下来我们先看集合排序的第一篇文章！

二. List内容回顾

在对List集合进行排序之前，我们还是先来复习一下List集合，看看前几天 壹哥 带各位复习的集合内容，你是否还能记得起来。

1. List简介

List是一个有序列表接口，内部允许存放重复的元素。该接口的常用子类如下：

• ArrayList：底层基于 数组实现，查询快，增删慢，轻量级，但是线程不安全。
• LinkedList：底层基于 双向链表实现，增删快，查询慢，也是线程不安全。
• Vector：底层基于 数组实现，重量级，线程安全，但目前使用较少。

2. List常用方法

• void add(int index, Object element)：添加对象element到位置index上；
• boolean addAll(int index, Collection collection)：在index位置后添加容器collection中所有的元素；
• Object get(int index)：取出下标为index的位置的元素；
• int indexOf(Object element)：查找对象element 在List中第一次出现的位置；
• int lastIndexOf(Object element): 查找对象element 在List中最后出现的位置；
• Object remove(int index)：删除index位置上的元素；
• ListIterator listIterator(int startIndex)：返回一个ListIterator 跌代器，开始位置为startIndex；
• List subList(int fromIndex, int toIndex): 返回一个子列表List，元素存放为从 fromIndex 到toIndex之前的一个元素；
• void sort(Comparator<? super E> c)：对集合中的元素进行排序的方法。

3. List集合排序方式简介

对于List集合来说，如果我们要对其进行排序，其实主要是对其内部的数据元素进行排序。所以，此时List集合的排序问题，主要就被转换成了对其内部数据元素的排序问题了。而我们从上面的List常用方法介绍中可以看到，List集合其实给我们提供了一个sort()排序方法，我们可以利用该方法对数据元素进行排序。

如果List集合中的数据元素，其类型是数值型的，sort()方法会基于默认的规则对数字进行升序排列。但如果其数据类型是对象类型，那么该怎么排序呢？这时我们要想实现对集合元素的排序，就需要把元素对象先进行排序处理，可以对数据元素进行 自定义排序 或者 实现Java中的比较器接口。所以总的来看，我们对List集合排序时，可以有4种实现方案：

• 1. 对简单数值型元素，直接调用集合对象的sort()方法或者是Collections#sort()方法进行自然排序；
• 2. 自定义对象排序：对复杂对象类型，我们可以根据自定义对象的数据结构，自定义排序规则来实现；
• 3. 实现Java中的比较器接口排序：对复杂对象，也可以实现Java中的两个常用接口，Comparable和Comparator;
• 4. 利用Lambda语法对List集合进行排序。

接下来 壹哥 就会编写几个案例，分别演示一下这几种排序方式的代码实现效果。

三. 对数值型直接sort

1. sort排序案例

首先我们定义一个存储Integer整型的List集合，对其直接采用sort()方法进行自然排序，代码如下所示：

    public static void main(String[] args){//对数值型数据,直接采用sort()方法进行排序.List<Integer> sortList = new ArrayList<>();sortList.add(9);sortList.add(1);sortList.add(6);sortList.add(2);System.out.println("排序之前的集合="+sortList);sortList.sort(null);//也可以使用下面的方法来进行升序排列//Collections.sort(list);System.out.println("排序之后的集合="+sortList);}

代码执行结果如下图所示：

我们会发现，在集合排序之前，数据元素是杂乱无序的；排序之后，集合中的数据元素自动进行了升序排列。如果我们需要进行降序排列，可以使用Collections#reverse(list)方法。

2. List#sort()方法源码分析

这时候，你可能很好奇，List中的sort()方法为什么可以对数据进行自然排序呢？为什么是升序而不是降序？它的内部是怎么实现的呢？要想搞清楚这个问题，我们还是来看看sort()方法的源码吧。

    default void sort(Comparator<? super E> c) {Object[] a = this.toArray();Arrays.sort(a, (Comparator) c);ListIterator<E> i = this.listIterator();for (Object e : a) {i.next();i.set((E) e);}}

从上面的源码中可以看出，sort()方法的功能如下：

• 整个sort()方法首先会传入一个Comparator比较器作为参数，用于作为比较的标准；
• 然后会把list对象转成一个Object数组，并利用Arrays.sort()方法对这个数组进行排序；
• 排序之后，再利用iterator重新改变list集合中的内容。

由此可知，List#sort()方法的排序功能，其内部主要是依赖Arrays.sort()方法来实现的，所以我们就需要继续弄清楚Arrays.sort()方法是怎么实现的了，其源码如下：

    public static <T> void sort(T[] a, Comparator<? super T> c) {if (c == null) {sort(a);} else {if (LegacyMergeSort.userRequested)legacyMergeSort(a, c);elseTimSort.sort(a, 0, a.length, c, null, 0, 0);}}

Arrays.sort()方法的主要执行逻辑如下：

• 首先在sort()方法中会进行if/else分支判断，根据Comparator对象是否为空共分为2种情况。
• 当Comparator对象为空时，会调用内部的sort()方法；
• 当LegacyMergeSort.userRequested为true时，会采用legacyMergeSort()进行排序，否则采用TimSort.sort排序。

3. 归并排序简介

LegacyMergeSort方法其实是JDK 7中为了兼容之前版本而提供的一个归并排序，而TimSort则是优化后的归并排序。

这里所谓的归并排序(Merge Sort)，是建立在归并操作上的一种有效、稳定的排序算法。该算法采用了分治思想(Divide and Conquer)，其思路就是将已排序的子序列进行合并，得到一个完全有序的序列。也就是说，该算法会先使每个子序列进行排序，最后将两个有序表合并成一个有序表，称为二路归并。

归并排序其核心原理就是将一个数组分割成两个子数组，并对每个子数组进行排序，最后再归并起来。每个数组排序时会在相邻的两个元素之间进行比较交换，相同元素的相对位置不会发生变化，属于是一种稳定性的算法。

4. legacyMergeSort()方法源码分析

因为在Arrays#sort()方法中调用了legacyMergeSort()方法，所以我们也要来看看该方法的源码，如下：

    private static <T> void legacyMergeSort(T[] a, Comparator<? super T> c) {//定义新数组，供排序后使用T[] aux = a.clone();if (c==null)mergeSort(aux, a, 0, a.length, 0);elsemergeSort(aux, a, 0, a.length, 0, c);}private static void mergeSort(Object[] src,Object[] dest,int low, int high, int off,Comparator c) {int length = high - low;//如果数组长度小于7，则使用插入排序，//即每个元素和在它前面的元素一一比较，若小于前面的元素，就交换两者的位置。// Insertion sort on smallest arraysif (length < INSERTIONSORT_THRESHOLD) {for (int i=low; i<high; i++)for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)swap(dest, j, j-1);return;}// 在这里利用分治思想，进行拆分，递归调用插入排序。// 在这里将待排序的数组一分为二，利用递归思想，不断地切分数组，// 当切分后的数组长度小于7时，还是利用插入排序进行排序，然后再归并，即可完成排序功能。// Recursively sort halves of dest into srcint destLow  = low;int destHigh = high;low  += off;high += off;int mid = (low + high) >>> 1;mergeSort(dest, src, low, mid, -off, c);mergeSort(dest, src, mid, high, -off, c);//合并相邻的两个已排好的数组。若左边最大的值 < 右边最小的值，说明数组已排好序，直接拷贝// If list is already sorted, just copy from src to dest.  This is an// optimization that results in faster sorts for nearly ordered lists.if (c.compare(src[mid-1], src[mid]) <= 0) {System.arraycopy(src, low, dest, destLow, length);return;}//在这里进行归并排序// Merge sorted halves (now in src) into destfor(int i = destLow, p = low, q = mid; i < destHigh; i++) {if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)dest[i] = src[p++];elsedest[i] = src[q++];}}    

5. TimSort.sort()方法源码

在Arrays.sort()方法中，当系统检测到是新版本的JDK时，会调用TimSort.sort()方法进行排序，其源码如下：

    static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,T[] work, int workBase, int workLen) {assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;//获取待排序数组的元素个数，若个数小于2，则无需排序。int nRemaining  = hi - lo;if (nRemaining < 2)return;  // Arrays of size 0 and 1 are always sorted//传入的待排序数组若小于阈值MIN_MERGE(Java实现中为32，Python实现中为64)，//则调用 binarySort，这是一个不包含合并操作的 mini-TimSort，是一种优化后的二分排序。// If array is small, do a "mini-TimSort" with no mergesif (nRemaining < MIN_MERGE) {int initRunLen = countRunAndMakeAscending(a, lo, hi, c);//使用二分查找法，将后续数字插入到之前已排序的数组中，binarySort 对数组 a[lo:hi] 进行排序，//并且a[lo:start] 是已经排好序的。binarySort(a, lo, hi, lo + initRunLen, c);return;}//在执行binarySort方法时需要将lo + initRunLen后的数字,依此插入前面的升序序列中。//若待排序数组,大于阈值MIN_MERGE，则直接进行排序。/*** 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.*/TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);int minRun = minRunLength(nRemaining);do {// Identify next runint runLen = countRunAndMakeAscending(a, lo, hi, c);// 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, c);runLen = force;}// Push run onto pending-run stack, and maybe mergets.pushRun(lo, runLen);ts.mergeCollapse();// Advance to find next runlo += runLen;nRemaining -= runLen;} while (nRemaining != 0);// Merge all remaining runs to complete sortassert lo == hi;ts.mergeForceCollapse();assert ts.stackSize == 1;}

TimSort算法是一种起源于归并排序和插入排序的混合排序算法，最初是Tim Peters在2002年时，在Python语言中提出的，主要是为了能让真实世界中的各种数据可以有较好的性能。

TimSort 对归并排序做了大量优化，优化了归并排序中反向排序时的输入表现，并对正向排序的输入减少了回溯。

TimSort的核心思想其实就是分区与合并。

分区：扫描一次数组，把其内部元素变成连续的正序列(正序列即升序)。如果是反序列，则把分区里的元素进行反转。 如把1，2，3，6，4，5，8，6，4 分区为[1,2,3,6]，[4,5,8]，[6,4]，然后再进行反转，[1,2,3,6]，[4,5,8]，[4,6]

合并：采用某种策略优化合并的顺序。

以上就是 壹哥 对Arrays#sort()方法的源码简介，大家简单了解即可。至此，壹哥 就先带各位用sort()方法实现了对集合的排序，接下来我会再下一篇文章中，讲解其他的排序方式，敬请关注哦。