手记

Java SDK中的排序算法小议 - 02 单轴快排

在前边的文章里,我们分析了最简单的merge sort。这篇文章我们继续来看看针对primitive类型排序的quick sort(即快排)是如何实现的。

虽然现行的JDK中采用的是优化过的DualQuickSort,但是相对复杂了很多。如果直接去看,会比较吃力,所以我们可以先去分析一下普通的单轴快排,然后回过头再来看DualQuickSort,会更容易一些。

在JDK 1.7中,DualQuickSort被首次引入。所以我们这里采用JDK 1.6的源码,来看看之前版本的单轴快排是怎么实现的。

单轴快排 - quick sort

调用流程

先简单分析一下它的调用流程

入口函数是+Arrays.sort(int[] a),涉及到的函数有

  • -Arrays.sort1(int x[], int off, int len)
  • -Arrays.swap((int x[], int a, int b)
  • -Arrays.med3(int x[], int a, int b, int c)
  • -Arrays.vecswap(int x[], int a, int b, int n)

代码实现

从上面的执行流程里边,我们可以比较直观地了解到快排的一个基本思想 - 分治思想。看起来与前边我们分析的merge sort很像,那他们两个主要的区别在哪里呢?

这里有一个简单的对比:

  • merge sort - 由下到上 - 先处理子问题,然后再合并(重点 - 合并函数)
  • quick sort - 由上到下 - 先对父问题分区,然后处理子问题(重点 - 分区函数)

同样的,我从上述流程中标记了几个关键的点,依次来进行分析。

C

针对小数组的优化,直接使用insertion sort。具体的实现和前边分析的merge sort一样。这里不再赘述。

D

针对选取pivot的优化,使用三数或者九数取中获取一个尽量接近与中位数的轴心点。从代码实现可以看到九数取中就是执行3次三数取中。实现的代码如下所示

    /**
     * Returns the index of the median of the three indexed integers.
     */
    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));
    }

三目运算符虽然紧凑,但是阅读性稍微差了一点。如果改写成普通的if-else,会直观一些,如下

    private static int med3(int x[], int a, int b, int c) {
        if (x[a] < x[b]) {
            if (x[b] < x[c]) return b;          // x[a] < x[b] < x[c]
            else if (x[a] < x[c]) return c;     // x[a] < x[c] < x[b]
            else return a;                      // x[c] < x[a] < x[b]
        } else {
            if (x[b] > x[c]) return b;          // x[a] > x[b] > x[c]
            else if (x[a] > x[c]) return c;     // x[a] > x[c] > x[b]
            else return a;                      // x[c] > x[a] > x[b]
        }
    }

即这里是手动将输入的三个下标对应的元素进行比较,穷举了所有的6种情况。

I

这部分逻辑是非常重要的一环 - 分区,根据pivot的值,将原来的数组划分为以下4个区域

我们看一下代码

        int v = x[m]; // The pivot

        // Establish Invariant: v* (<v)* (>v)* v*
        int a = off, b = a, c = off + len - 1, d = c;
        while(true) {
            while (b <= c && x[b] <= v) {   // (1)
                if (x[b] == v)              // (2)
                    swap(x, a++, b);
                b++;
            }
            while (c >= b && x[c] >= v) {   // (3)
                if (x[c] == v)              // (4)
                    swap(x, c, d--);
                c--;
            }
            if (b > c)
                break;
            swap(x, b++, c--);              // (5)
        }

关于注释中的invariant,可以简单地理解为一种约束条件(更多相关资料可以阅读参考资料里的链接)。如果我们把上边分区的示意图看成一种约束条件,那其实这部分代码就是建立分区的过程。

这部分的关键是理解a, b, c, d四个变量的含义。他们是两类游标

  • a/d - 从左右两端分别向中间移动。其中a之前, d之后都是等于pivot的值的元素
  • b/c - 从左右两端分别向中间移动。b之前的元素都是小于等于pivot的值的元素,c之后的元素都是大于等于pivot的值的元素

然后我们再来看上面的代码,其中

  • (1)/(3)是分别移动游标b/c,以找到符合b/c条件的区间,如果不满足条件,就停下来。通过(5)来进行交换,然后继续循环,直到b/c相遇,结束循环。
  • (2)/(4)则是在进行(1)/(3)的同时,将等于pivot的值的元素分别通过交换移动到数组的两端。

J

这个阶段就是将两端等于pivot的值移动到中间,完成整个分区动作。完成之后的效果如下

这一部分的代码比较少,如下

        // 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);

直接看对s的计算比较抽象。同样可以借助画图,来理解作者的意图。经过上个阶段的分区之后,各个游标大概是这个样子

这个图其实与I里边的插图是一致的,即

区域 含义
a-off =pivot
b-a <pivot
d-c >pivot
n-d-1 =pivot

a-offb-a为例,只需要找出两者中较小的值s,然后将两个区间交换s次就可以将=pivot部分的元素移动到<pivot区间的右边。

d-cn-d-1也是同样的道理。

具体的区间交换代码较为简单,如下

    /**
     * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
     */
    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);
    }

K

有了前边的分析,这部分代码看起来就简单多了。此处就是将左右两个子区间进行递归调用,最终完成整个排序。

即将<pivot的区间和>pivot的区间分别进行递归调用

代码如下

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

小结

总结一下,我们从JDK里早期版本的快排 - 单轴快排入手,详细分析了整个代码运行的过程。并且在绘制了辅助的图形,方便理解对应的代码。

接下来我们可以据此为基础,学习双轴快排是如何实现的。

参考资料

2人推荐
随时随地看视频
慕课网APP

热门评论

学习了,感谢作者分享?

查看全部评论