Java排序实现的心得分享

1.概述
排序和查找是程序设计里的两类非常基本的问题，而现在也存在很多经典的算法用于解决这两类问题，本文主要对java中排序算法实现进行一个基本的探讨，希望能够起到抛砖引玉的作用。在此之前，首先问各位几个问题：你能写出一个正确的快排吗？快排在什么情况下真正的快？你的快排足够快吗？还可以进一步优化吗？带着这些问题，我们来看看jre7中快排是如何实现的吧。

Jre7中排序的实现类是DualPivotQuickSort.java，相比jre6有一些改变，主要发生在两个地方，一个是insertion sort的实现上，另一个是QuickSort实现中pivot从一个变成了两个。我们以int型的数组为例，该类中有个排序实现的核心方法，该方法的原型为

代码如下:

void sort(int[] a, int left, int right, boolean leftmost)

参数a为需要排序的数组，left代表需要排序的数组区间中最左边元素的索引，right代表区间中最右边元素的索引，leftmost代表该区间是否是数组中最左边的区间。举个例子：
数组：[2, 4, 8, 5, 6, 3, 0, -3, 9]可以分成三个区间(2, 4, 8){5, 6}<3, 0, -3, 9>
对于()区间，left=0, right=2, leftmost=true
对于 {}区间, left=3, right=4, leftmost=false，同理可得<>区间的相应参数

当区间长度小于47时，该方法会采用插入排序；否则采用快速排序。

2. 插入排序实现
当leftmost为true时，它会采用传统的插入排序(traditional insertion sort)，代码也较简单，其过程类似打牌时抓牌插牌：


代码如下:

for (int i = left, j = i; i < right; j = ++i) {
                    int ai = a[i + 1];
                    while (ai < a[j]) {
                        a[j + 1] = a[j];
                        if (j-- == left) {
                            break;
                        }
                    }
                    a[j + 1] = ai;
                }

传统插入排序代码
当leftmost为false时，它采用一种新型的插入排序（pair insertion sort），改进之处在于每次遍历前面已排好序的数组需要插入两个元素，而传统插入排序在遍历过程中只需要为一个元素找到合适的位置插入。对于插入排序来讲，其关键在于为待插入元素找到合适的插入位置，为了找到这个位置，需要遍历之前已经排好序的子数组，所以对于插入排序来讲，整个排序过程中其遍历的元素个数决定了它的性能。很显然，每次遍历插入两个元素可以减少排序过程中遍历的元素个数，其实现代码如下：


代码如下:

for (int k = left; ++left <= right; k = ++left) {
                    int a1 = a[k], a2 = a[left];

if (a1 < a2) {
                        a2 = a1; a1 = a[left];
                    }
                    while (a1 < a[--k]) {
                        a[k + 2] = a[k];
                    }
                    a[++k + 1] = a1;

while (a2 < a[--k]) {
                        a[k + 1] = a[k];
                    }
                    a[k + 1] = a2;
                }

现在有个问题：为什么最左边的区间采用传统插入排序，其他的采用成对插入排序呢？加入用上述成对插入排序代码替换传统插入排序代码，会出现什么问题呢？期待大家自己来回答。。。
3. 快速排序实现
Jre7中对快速排序也做了改进，传统的快速排序是选取一个pivot（jre6种选取pivot的方法是挑选出数组最左边，中间和最右边位置的元素，将其中数值大小排在中间的元素作为pivot），然后分别从两端向中间遍历，把左边遍历过程中遇到的大于pivot的值和右边遍历中遇到的小于等于pivot的值进行交换，当遍历相遇后，插入pivot的值；这样就使得pivot左边的值均小于或等于pivot，pivot右边的值大于pivot；接下来再采用递归的方式对左边和右边分别进行排序。

通过上述分析，我们可以看到：插入排序的每一步是使数组的一个子区间绝对有序，而每一次循环的本质是使这个子区间不断扩大，所以我们可以看到其优化的方向是使每次循环遍历尽可能的使子区间扩大的速度变快，所以上面把每次遍历插入一个元素优化成每次插入两个元素。当然肯定有人会问，那为什么不把这个数字变得更大一点呢？比如每次遍历插入5个，10个。。。很显然，这样是不行，它的一个极端情况就是每次遍历插入n个（n为数组长度）。。。至于为什么，大家自己回答吧。

对于快速排序来讲，其每一次递归所做的是使需要排序的子区间变得更加有序，而不是绝对有序；所以对于快速排序来说，其性能决定于每次递归操作使待排序子区间变得有序的程度，另一个决定因素当然就是递归次数。快速排序使子区间变得相对有序的关键是pivot，所以我们优化的方向也应该在于pivot，那就增加pivot的个数吧，而且我们可以发现，增加pivot的个数，对递归次数并不会有太大影响，有时甚至可以使递归次数减少。和insert sort类似的问题就是，pivot增加为几个呢？很显然，pivot的值也不能太大；记住，任何优化都是有代价的，而增加pivot的代价就隐藏在每次交换元素的位置过程中。关子貌似卖的有点大了。。。下面我们就来看看pivot的值为2时，快速排序是如何实现的吧。其实现过程其实也不难理解：
1.  首先选取两个pivot，pivot的选取方式是将数组分成近视等长的六段，而这六段其实是被5个元素分开的，将这5个元素从小到大排序，取出第2个和第4个，分别作为pivot1和pivot2；
2.  Pivot选取完之后，分别从左右两端向中间遍历，左边遍历停止的条件是遇到一个大于等于pivot1的值，并把那个位置标记为less；右边遍历的停止条件是遇到一个小于等于pivot2的值，并把那个位置标记为great
3.  然后从less位置向后遍历，遍历的位置用k表示，会遇到以下几种情况:
a.  k位置的值比pivot1小，那就交换k位置和less位置的值，并是less的值加1；这样就使得less位置左边的值都小于pivot1，而less位置和k位置之间的值大于等于pivot1
b.  k位置的值大于pivot2，那就从great位置向左遍历，遍历停止条件是遇到一个小于等于pivot2的值，假如这个值小于pivot1，就把这个值写到less位置，把less位置的值写道k位置，把k位置的值写道great位置，最后less++，great--；加入这个值大于等于pivot1，就交换k位置和great位置，之后great—
4.  完成上述过程之后，带排序的子区间就被分成了三段（<pivot1, pivot1<=&&<=pivot2,>pivot2），最后分别对这三段采用递归就行了。


代码如下:

/*
             * Partitioning:
             *
             *   left part           center part                   right part
             * +--------------------------------------------------------------+
             * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
             * +--------------------------------------------------------------+
             *               ^                          ^       ^
             *               |                          |       |
             *              less                        k     great
             *
             * Invariants:
             *
             *              all in (left, less)   < pivot1
             *    pivot1 <= all in [less, k)     <= pivot2
             *              all in (great, right) > pivot2
             *
             * Pointer k is the first index of ?-part.
             */

Jre7中对排序实现的核心内容就如上所述，具体细节可参见相应类中的代码，如发现错误或不妥之处，望指正。