Arrays.sort()方法到底用的什么排序算法(1)

今天有人问我java里面的sort 方法 到底是什么什么排序方法。刚开始我也很蒙 一直在用却说不出所以然来。所以我今天就看下源码

    public static void sort(Object[] a) {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a);
        else
            ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
    }

legacyMergeSort算法

	private static void legacyMergeSort(Object[] a) {
		//定义心的数组，作为排序后的对象
        Object[] aux = a.clone();
        mergeSort(aux, a, 0, a.length, 0);
    }
	private static void mergeSort(Object[] src,
                                  Object[] dest,
                                  int low,
                                  int high,
                                  int off) {
        int length = high - low;

        // 数组大小如果小于7，则使用插入排序
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i=low; i<high; i++)
                for (int j=i; j>low &&
                         ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
        }

        // 利用分治思想，进行拆分，递归调用插入排序
        int destLow  = low;
        int destHigh = high;
        low  += off;
        high += off;
        int mid = (low + high) >>> 1;
        mergeSort(dest, src, low, mid, -off);
        mergeSort(dest, src, mid, high, -off);

        // 合并相邻两个已排好的部分，若左边最大的  小于  右边最小的，
        // 说明数组已经排好顺序，直接拷贝
        if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // 进行归并排序，
        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

总结

平均时间复杂度：O(nlogn)
最佳时间复杂度：O(n)
最差时间复杂度：O(nlogn)
空间复杂度：O(n)
排序方式：In-place
稳定性：稳定

上面的代码的优化核心部分就是

// 改进归并排序在归并时先判断前段序列的最大值与后段序列最小值的关系再确定是否进行复制比较。
	//如果前段序列的最大值小于等于后段序列最小值，则说明序列可以直接形成一段有序序列不需要再归并，
	//反之则需要。所以在序列本身有序的情况下时间复杂度可以降至O(n)
    if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
        System.arraycopy(src, low, dest, destLow, length);
        return;
    }

归并排序算法中，归并最后到底都是相邻元素之间的比较交换，并不会发生相同元素的相对位置发生变化，故是稳定性算法。

然而在新的jdk 版本中这个排序几乎不在用了

    public static void sort(Object[] a) {
        // 只有老的JDK 版本这个值默认值 才会生效
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a);
        else
            ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
    }

所以现在基本用的都是ComparableTimSort.sort 关于这个算法 我会在下篇文章中详细讲解。

欢迎大家 关注 私信 如果有写的不对的地方欢迎指出。