深入了解Arras.sort()与Collections.sort()的区别

落日映苍穹つ 2022-07-14 15:48 156阅读 0赞

先来看看Arrays.sort()源码一步一步追踪下去

public static void sort(int[] a) {
            DualPivotQuicksort.sort(a);
        }

public static void sort(int[] a) {
            sort(a, 0, a.length - 1);
        }

public static void sort(int[] a, int left, int right) {
            // Use Quicksort on small arrays
            if (right - left < QUICKSORT_THRESHOLD) {
                sort(a, left, right, true);
                return;
            }
    
            /*
             * Index run[i] is the start of i-th run
             * (ascending or descending sequence).
             */
            int[] run = new int[MAX_RUN_COUNT + 1];
            int count = 0; run[0] = left;
    
            // Check if the array is nearly sorted
            for (int k = left; k < right; run[count] = k) {
                if (a[k] < a[k + 1]) { // ascending
                    while (++k <= right && a[k - 1] <= a[k]);
                } else if (a[k] > a[k + 1]) { // descending
                    while (++k <= right && a[k - 1] >= a[k]);
                    for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
                        int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
                    }
                } else { // equal
                    for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
                        if (--m == 0) {
                            sort(a, left, right, true);
                            return;
                        }
                    }
                }
    
                /*
                 * The array is not highly structured,
                 * use Quicksort instead of merge sort.
                 */
                if (++count == MAX_RUN_COUNT) {
                    sort(a, left, right, true);
                    return;
                }
            }
    
            // Check special cases
            if (run[count] == right++) { // The last run contains one element
                run[++count] = right;
            } else if (count == 1) { // The array is already sorted
                return;
            }
    
            /*
             * Create temporary array, which is used for merging.
             * Implementation note: variable "right" is increased by 1.
             */
            int[] b; byte odd = 0;
            for (int n = 1; (n <<= 1) < count; odd ^= 1);
    
            if (odd == 0) {
                b = a; a = new int[b.length];
                for (int i = left - 1; ++i < right; a[i] = b[i]);
            } else {
                b = new int[a.length];
            }
    
            // Merging
            for (int last; count > 1; count = last) {
                for (int k = (last = 0) + 2; k <= count; k += 2) {
                    int hi = run[k], mi = run[k - 1];
                    for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
                        if (q >= hi || p < mi && a[p] <= a[q]) {
                            b[i] = a[p++];
                        } else {
                            b[i] = a[q++];
                        }
                    }
                    run[++last] = hi;
                }
                if ((count & 1) != 0) {
                    for (int i = right, lo = run[count - 1]; --i >= lo;
                        b[i] = a[i]
                    );
                    run[++last] = right;
                }
                int[] t = a; a = b; b = t;
            }
        }

![Center][]  
我们发现在底层实现的时候当整形数组大小不超过286时使用的是快排，如果数组比较大了，然后判断是否有序，如果并没有结构化那么继续使用快排，否则使用归并排序（因为在数组基本有序的情况下，快排的时间复杂度N^2，所以此时使用归并排序性能更加），因此Arrays.sort()的时间复杂度是N\*LogN

## 再来看看Collections.sort(List)实现源码 ##

public static <T extends Comparable<? super T>> void sort(List<T> list) {
            Object[] a = list.toArray();
            Arrays.sort(a);
            ListIterator<T> i = list.listIterator();
            for (int j=0; j<a.length; j++) {
                i.next();
                i.set((T)a[j]);
            }
        }

可以看到Collections.sort()实际上是重新创建了一个数组，然后利用Arrays.sort()进行排序再插入进去

[Center]: /images/20220709/562f2710a5a245168f05401a8ad9e0f5.png