排序算法在jdk源码中的应用

本文旨在分析排序算法在jdk源码中的应用，重点对java的集合排序实现进行探究，内容不会面面俱到，侧重整体结构性的分析以及部分笔者研读时受到启发的地方，希望能起到抛砖引玉的作用。

序

排序是一个很常用算法，那么在一个项目中我们总要自己实现排序算法么，显然不是，高级语言往往都提供了现成的排序算法(比如笔者最早接触c语言的时候用到的qsort和bsearch，快排和二分函数)，面向对象语言则对排序做了更好的集成，而这些基本能够满足我们一般项目的要求。今天我们以java为例，分析排序算法的应用。

谈及java中的排序，要说到两个类Arrays和Collections。两者都是对数据集合进行操作的工具类，前者针对数组，后者针对集合(Collection)。

示例

代码只展示用法，没有实际意义。

public static void main(String[] args)
{
    String[] namesStrings = new String[10];
    Arrays.sort(namesStrings);//1

    List<String> list = new ArrayList<>();
    Collections.sort(list);//2

    int a[] = new int[10];
    Arrays.sort(a);//3

}

1处Arrays.sort对object[]进行排序

看源码(jdk1.7)

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

这里如果你使用的是1.7之前的src，很可能看到的是如下代码

public static void sort(Object[] a) {
    Object[] aux = a.clone();
    mergeSort(aux, a, 0, a.length, 0);
}   

我们看1.7中sort(Object[] a)中的legacyMergeSort

private static void legacyMergeSort(Object[] a) {
    Object[] aux = a.clone();
    mergeSort(aux, a, 0, a.length, 0);
}

顾名思义，这是旧版本遗留的mergesort算法，如果用户设定可以指定使用此方法，否则使用新的ComparableTimSort类提供的新的排序算法。

2处Collections.sort对集合进行排序

看源码(jdk1.7)

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    Object[] a = list.toArray();
    Arrays.sort(a); //调用Arrays对应object[]的排序算法
    ListIterator<T> i = list.listIterator();
    for (int j=0; j<a.length; j++) {
        i.next();
        i.set((T)a[j]);
    }
}

此处1.6和1.7是一样的，我们可以看出来在Collections内部是先将集合转成数组然后调用Arrays对对象数组的排序算法来进行排序，然后生成集合，这也是对Arrays的复用，因为Collection集合的概念(注意Collection和Collections)是后提出的，加入迭代器泛型参数等等，感兴趣的可以去扒一扒进化史。

上述我们可以看出对于对象数组或者集合，最终都是调用Arrays.sort（Object[]）方法，我们这里强调了对象数组，应为还有3对应的情况，原始数据类型，Arrays.sort针对基本类型重载了多个函数，使用快速排序我们后续看代码。

3处Arrays对基本类型数组排序

看源码(jdk1.7)

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

当然对应其他数据类型也都有函数，比如char数组

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

这里使用了快速排序，但不是普通的快速排序，而是DualPivot的快速排序，双基准的快速排序。

源码中的排序算法

归并排序中注意到的就是有一个阈值，小于阈值7则使用插入排序，然后就是两个数组的复用dst和src，建议仔细看递归调用的部分。

private static void mergeSort(Object[] src,
                              Object[] dest,
                              int low,
                              int high,
                              int off) {
    int length = high - low;

    // 小规模使用插入排序
    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;
    }

    // 递归的调用，注意dest和src的位置，将两个有序的序列放到src中
    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 list is already sorted, just copy from src to dest.  This is an
    // optimization that results in faster sorts for nearly ordered lists.
    if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
        System.arraycopy(src, low, dest, destLow, length);
        return;
    }

    // 将src中的两个部分合并到dst中
    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++];
    }
}

插入排序部分截取出来，比较简单，但是确定你能写出无误的插入排序么。

    // 小规模使用插入排序
    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;
    }

这里我们没有传入比较器，则使用对象自身的比较函数，我们代码中元素是String类型，其本身实现了Comparable接口，如果传入了比较器，则使用比较器来比较大小。

String实现Comparable接口

public final class String
    implements java.io.Serializable, Comparable<String>, CharSequence

compareTo方法

public int compareTo(String anotherString) {
    int len1 = value.length;
    int len2 = anotherString.value.length;
    int lim = Math.min(len1, len2);
    char v1[] = value;
    char v2[] = anotherString.value;

    int k = 0;
    while (k < lim) {
        char c1 = v1[k];
        char c2 = v2[k];
        if (c1 != c2) {
            return c1 - c2;
        }
        k++;
    }
    return len1 - len2;
}

快速排序的实现

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

调用了sort(int[] a, int left, int right)方法，

public static void sort(int[] a, int left, int right) {

    //小规模不使用快排，这里使用插入或者计数等方法 
    if (right - left < QUICKSORT_THRESHOLD) {
    sort(a, left, right, true);
    return;
    }

    //使用双基准快排   
    ...
    ....
}

文章篇幅有限，双基准排序和ComparableTimSort的sort方法在本文中不再分析。

总结

Collections对集合的排序最终还是归于Arrays对object[]的排序，旧版本使用归并排序，目前也有新的排序算法推出，这些对于我们上层使用者并无大影响，随着语言的发展，api的实现自然是向着高效安全的方向发展。对于基本数据类型，Arrays的sort方法使用双基准的快速排序实现。无论是归并还是快排，在问题规模小的时候都是使用简单排序来完成，比如对于基本类型的快排，问题规模小的时候使用COUNTING_SORT或者INSERTIONSORT来完成，对于类对象集合的归并排序，问题规模小的时候小于7，使用INSERTIONSORT来完成排序。对于源码的研读一是看起思想，排序算法的选择对应问题规模的考虑，二是看看基本算法的实现，读了本文后，希望读者能够耐心把jdk中的插入排序，计数排序，归并排序和快速排序分析一下，和自己写的有什么差别，这里的代码应该比网上贴出的私人代码更为靠谱。