Java程序员应当掌握的排序算法

今天总结一下JDK中采用的排序算法，主要出现在两个类中。

 

java.util.Arrays

 

static void sort(int[] a)

static void sort(int[] a, int fromIndex, int toIndex)

 

其他基本类型（byte，char，short，long，float，double）算法相同。float 和 double 多了两步long型本地转换的步骤，主要处理NaN值。

以上基本类型数组的排序方法的 采用了一个经过调优的快速排序法。

 

static <T> void sort(T[] a, Comparator<? super T> c)
static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c)
（java.util.Collections 类的 sort方法 实际调用了上面的方法）

对象数组则 采用了经过修改的归并排序算法。（如果低子列表中的最高元素小于高子列表中的最低元素，则忽略合并）。

 

java.util.PriorityQueue

 

一个基于优先级堆的无界优先级队列（基于堆排序算法）

 

【基础原理】
快速排序（QuickSort） 时间复杂度  平均O(nlogn)  最坏O(n2)  空间复杂度 O(nlogn) 不稳定
算法：

# 选取中枢点
swap a[1,rand(1,n)]

# 以中枢点为界分割成大小两部分
k = 1
for i = 2:n, if a[i] < a[1], swap a[++k,i]
swap a[1,k]
→ invariant: a[1..k-1] < a[k] <= a[k+1..n]

# 对两部分做递归排序
sort a[1..k-1]
sort a[k+1,n]

 

虽然不够稳定，但是实际应用中快速排序比大部分排序算法都要快。

归并排序（MergeSort） 时间复杂度 O(nlogn)  空间复杂度 O(1)  稳定
算法：

# 数组均分为两块
m = n / 2

# 两块分别递归
sort a[1..m]
sort a[m+1..n]

# 使用中间数组做排序
b = copy of a[1..m]
i = 1, j = m+1, k = 1
while i <= m and j <= n,
    a[k++] = (a[j] < b[i]) ? a[j++] : b[i++]
    → invariant: a[1..k] in final position
while i <= m,
    a[k++] = b[i++]
    → invariant: a[1..k] in final position

 

归并排序比堆排序快，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。

最终归并排序依靠其稳定性拿到了JDK排序中的头把交椅，被应用于使用最广泛的对象集合排序中。

堆排序（HeapSort） 时间复杂度 O(nlogn)  空间复杂度 O(1) 不稳定
算法：

# 构造堆
for i = n/2:1, sink(a,i,n)
→ invariant: a[1,n] in heap order

# 循环下沉
for i = 1:n,
    swap a[1,n-i+1]
    sink(a,1,n-i)
    → invariant: a[n-i+1,n] in final position
end

# 从 i 到 a[1..n] 递归sink
function sink(a,i,n):
    # {lc,rc,mc} = {left,right,max} child index
    lc = 2*i
    if lc > n, return # no children
    rc = lc + 1
    mc = (rc > n) ? lc : (a[lc] > a[rc]) ? lc : rc
    if a[i] >= a[mc], return # heap ordered
    swap a[i,mc]
    sink(a,mc,n)

 
堆排序适合于数据量非常大的场合，由于较少的空间消耗，在移动设备中，堆排序是首选。(相比使用递归的快速排序，归并排序，没有堆栈溢出的风险）

 

【代码分析】

相比来说快速排序的排序运用最为广泛，也是算法演变最多的一种。我们看分析下JDK中的快速排序。

 

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

    private static void sort1(int x[], int off, int len) {
    // 小于7时使用插入排序法
    // Insertion sort on smallest arrays
    if (len < 7) {
        for (int i=off; i<len+off; i++)
        for (int j=i; j>off && x[j-1]>x[j]; j--)
            swap(x, j, j-1);
        return;
    }

    // Choose a partition element, v
    int m = off + (len >> 1);       // Small arrays, middle element
    //根据当前数组大小确定选取枢轴策略
    //size=7时，直接取中间元素作为枢轴    
    //7<size<=40时，取数组头中尾三个节点的中数作为枢轴    
    //size>40时,将数组8等分后获取9个节点值得中数作为枢轴 
    if (len > 7) {
        int l = off;
        int n = off + len - 1;
        if (len > 40) {        // Big arrays, pseudomedian of 9
        int s = len/8;
        l = med3(x, l,     l+s, l+2*s);
        m = med3(x, m-s,   m,   m+s);
        n = med3(x, n-2*s, n-s, n);
        }
        m = med3(x, l, m, n); // Mid-size, med of 3
    }
    int v = x[m];

    // Establish Invariant: v* (<v)* (>v)* v*
    //这一段代码比较难理解,也是关键点。基本思路是：
    //  先将数组交换为 v* (<v)* (>v)* v* 的格局，即中值向两边移动
    //  再将相同的数移向数组的中部。
    //算法一个特点是中值会全部排序到位，当取到重复率高的值时，以后的排序对象就会缩小很多
    //论文中提到，这里等效于著名的“荷兰国旗问题”，该方法对于高度重复的数组整体排序时间节省20％
    int a = off, b = a, c = off + len - 1, d = c;
    while(true) {
        while (b <= c && x[b] <= v) {
        if (x[b] == v)
            swap(x, a++, b);
        b++;
        }
        while (c >= b && x[c] >= v) {
        if (x[c] == v)
            swap(x, c, d--);
        c--;
        }
        if (b > c)
        break;
        swap(x, b++, c--);
    }

    // Swap partition elements back to middle
    int s, n = off + len;
    s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
    s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);

    // Recursively sort non-partition-elements
    if ((s = b-a) > 1)
        sort1(x, off, s);
    if ((s = d-c) > 1)
        sort1(x, n-s, s);
    }

    // 这个函数 将分到两边的数移向数组的中部
    private static void vecswap(int x[], int a, int b, int n) {
    for (int i=0; i<n; i++, a++, b++)
        swap(x, a, b);
    }

    private static int med3(int x[], int a, int b, int c) {
    return (x[a] < x[b] ?
        (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
        (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
    }

    private static void swap(int x[], int a, int b) {
    int t = x[a];
    x[a] = x[b];
    x[b] = t;
    }

 （ 更详细的描述参考 Jon L. Bentley 和 M. Douglas McIlroy  的论文《Engineering a Sort Function》。JDK源码中除了把原文中C语言的宏换成了函数，其他完全一致。）

 

【参考】

经典参考书：《算法》（第4版）Sedgewick 著

一个不错的排序算法网站：www.sorting-algorithms.com

论文原文：http://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/421/09/bentley93engineering.pdf