快速排序的实现及优化方法

Contents

1. 快速排序的基本实现
2. 快速排序的优化及改进方法
3. 参考链接

快速排序的基本实现

快速排序算法是一种基于交换的高效的排序算法，它采用了分治法的思想：

从数列中取出一个数作为基准数（枢轴，pivot）。
将数组进行划分(partition)，将比基准数大的元素都移至枢轴右边，将小于等于基准数的元素都移至枢轴左边。
再对左右的子区间重复第二步的划分操作，直至每个子区间只有一个元素。

具体实现如下：

public class QuickSort {
    private static int partition(Comparable[] a, int lo, int hi){
        //partition array into a[lo..i - 1], a[i], a[i + 1..hi]
        int i = lo, j = hi + 1;
        Comparable v = a[lo];
        while (true){
            while(Example.less(a[++i], v)) {}
            while(Example.less(v, a[--j])) {}
            if(i >= j) break;
            Example.exch(a, i, j);
        }
        Example.exch(a, lo, j); //place v = a[j] in the right location
        return j; //a[lo..j-1] <= a[j] <= a[j+1..hi]
    }

    public static void sort(Comparable[] a){
        Collections.shuffle(Arrays.asList(a));
        sort(a, 0, a.length - 1);
    }

    public static void sort(Comparable[] a, int lo, int hi){
        if(hi <= lo) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    public static void main(String[] args) {
        Integer[] a = {2,6,1,3,5,4};
        System.out.print("The array befor sort is ");
        Example.show(a);
        sort(a);
        System.out.print("The array after sort is ");
        Example.show(a);
    }
}

快速排序的优化及改进方法

切换到插入排序

对于小数组，快速排序比插入排序慢
因为递归，快速排序的sort()方法在小数组中也会调用自己

只需将递归的的函数出口，即

1	if(hi <= lo) return;

替换为

1	if(hi <= lo + M){Insertion.sort(a, lo, hi); return;}

其中转换参数M在5~15之间取值在大多数情况下都能令人满意

三取样切分

使用子数组的一小部分元素的中位数来切分数组，这样做得到的切分更好，但代价是需要计算中位数，人们发现将取样大小设为3并用大小居中的元素切分的效果最好。

快速三向切分法

在有大量重复元素的情况下，快速排序的递归性会使元素全部重复的子数组经常出现，这就有很大的改进潜力，将当前实现的线性对数级的性能提高到线性级别。

最短路径算法的发明者Dijkstra发布了一种最经典的三向切分快速排序算法，维护lt和gt两个指针，仍旧取中枢轴为v=a[lo]，分以下三种情况进行讨论：

a[i]小于v，将a[lt]和a[i]交换，将lt和i加1
a[i]大于v，将a[gt]和a[i]交换，将gt减1
a[i]等于v，将i加1

快速三向切分

下面是实现：

private static void sort(Comparable[] a, int lo, int hi){
        if(hi <= lo) return;
        int lt = lo, i = lo + 1, gt = hi;
        Comparable v = a[lo];
        while(i <= gt){
            int cmp = a[i].compareTo(v);
            if(cmp < 0) Example.exch(a, lt++, i++);
            else if(cmp > 0) Example.exch(a, i, gt--);
            else ++i;
        }// now a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]
        sort(a, lo, lt - 1);
        sort(a, gt + 1, hi);
    }

J.Bentley和D.McIlroy找到了一种新的快速三向切分的方法（Bentley-McIlroy 3-way partitioning），解决了重复元素不多的情况下交换次数过多的问题

第一阶段（重复循环直到i和j指针相遇）：

Scan i from left to right so long as (a[i] < a[lo]).
Scan j from right to left so long as (a[j] > a[lo]).
Exchange a[i] with a[j]
If (a[i] == a[lo])，exchange a[i] with a[p] and increment p.
If (a[j] == a[lo])，exchange a[j] with a[q] and decrement q.

整个过程如下图所示：

Phase 1

具体实现如下：

// Bentley-McIlroy 3-way partitioning
       int i = lo, j = hi + 1;
       int p = lo, q = hi + 1;
       while (true) {
           Comparable v = a[lo];
           while (less(a[++i], v))
               if (i == hi) break;
           while (less(v, a[--j]))
               if (j == lo) break;
           if (i >= j) break;
           exch(a, i, j);
           if (eq(a[i], v)) exch(a, ++p, i);
           if (eq(a[j], v)) exch(a, --q, j);
       }
       exch(a, lo, j);

第二阶段（将键值相等的键移到数组中间）：

Scan j and p from right to left and exchange a[j] with a[p].
Scan i and q from left to right and exchange a[i] with a[q].

整个过程如下图所示：

Phase2

具体实现如下图所示：

i = j + 1;
j = j - 1;
for (int k = lo + 1; k <= p; k++) exch(a, k, j--);
for (int k = hi; k >= q; k--) exch(a, k, i++);

类似的快排优化在JDK1.8的DualPivotQuicksort也实现过，具体可看其源码，很奇妙。

JasonRen's Blog

Hello World!