Java Arrays和Collections的sort()方法源码分析

Arrays:

Collections:

Arrays ：是对数组进行排序；

Collections ：是对列表进行排序；

1 @SuppressWarnings("unchecked")
2     public static <T extends Comparable<? super T>> void sort(List<T> list) {
3         list.sort(null);
4     }

我们在索引进去： Ctrl + 左键；

 1 @SuppressWarnings({"unchecked", "rawtypes"})
 2     default void sort(Comparator<? super E> c) {
 3         Object[] a = this.toArray();
 4         Arrays.sort(a, (Comparator) c);
 5         ListIterator<E> i = this.listIterator();
 6         for (Object e : a) {
 7             i.next();
 8             i.set((E) e);
 9         }
10     }

原来在Collections中底层是调用了 Arrays.sort() 方法；

而Arrays.sort()方法中：

 1 public static <T> void sort(T[] a, Comparator<? super T> c) {
 2         if (c == null) {
 3             sort(a);
 4         } else {
 5             if (LegacyMergeSort.userRequested)
 6                 legacyMergeSort(a, c);
 7             else
 8                 TimSort.sort(a, 0, a.length, c, null, 0, 0);
 9         }
10     }
11 
12     /** To be removed in a future release. */
13     private static <T> void legacyMergeSort(T[] a, Comparator<? super T> c) {
14         T[] aux = a.clone();
15         if (c==null)
16             mergeSort(aux, a, 0, a.length, 0);
17         else
18             mergeSort(aux, a, 0, a.length, 0, c);
19     }

 1 public static void sort(Object[] a) {
 2         if (LegacyMergeSort.userRequested)
 3             legacyMergeSort(a);
 4         else
 5             ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
 6     }
 7 
 8     /** To be removed in a future release. */
 9     private static void legacyMergeSort(Object[] a) {
10         Object[] aux = a.clone();
11         mergeSort(aux, a, 0, a.length, 0);
12     }

终于：

 1     @SuppressWarnings({"unchecked", "rawtypes"})
 2     private static void mergeSort(Object[] src,
 3                                   Object[] dest,
 4                                   int low,
 5                                   int high,
 6                                   int off) {
 7         int length = high - low;
 8 
 9         // Insertion sort on smallest arrays
10         if (length < INSERTIONSORT_THRESHOLD) {
11             for (int i=low; i<high; i++)
12                 for (int j=i; j>low &&
13                          ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
14                     swap(dest, j, j-1);
15             return;
16         }
17 
18         // Recursively sort halves of dest into src
19         int destLow  = low;
20         int destHigh = high;
21         low  += off;
22         high += off;
23         int mid = (low + high) >>> 1;
24         mergeSort(dest, src, low, mid, -off);
25         mergeSort(dest, src, mid, high, -off);
26 
27         // If list is already sorted, just copy from src to dest.  This is an
28         // optimization that results in faster sorts for nearly ordered lists.
29         if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
30             System.arraycopy(src, low, dest, destLow, length);
31             return;
32         }
33 
34         // Merge sorted halves (now in src) into dest
35         for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
36             if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
37                 dest[i] = src[p++];
38             else
39                 dest[i] = src[q++];
40         }
41     }

所以，事实上Collections.sort方法底层就是调用的Arrays.sort方法，而Arrays.sort使用了两种排序方法，快速排序和优化的归并排序。快速排序主要是对那些基本类型数据（int,short,long等）排序，而归并排序用于对Object类型进行排序。