三路快速排序

对于快速排序，如果排序的数组中有很多的重复数如10000个【1，9】的数就有很多重复数，由于快速排序的判定问题，会导致这些重复数移到一边从而大幅增加算法的运算时间。解决方法，就是进行三路排序，分层>,=,<.

下面来介绍三路排序算法：

分成3块<v,>v,=v,在<v和>v中递归调用排序方法，如果e==v则i++即可 当比较点e<v时，将i处元素与lt+1处元素交换位置,lt++,i++ 单e>v时交换i处的元素与gt-1处的元素，i不变，gt--； 这是最后排序完成的图像 将l处的元素与lt处的元素交换即可。

以下是算法实现：

package bobo.algo;

import java.util.*;

public class QuickSort3Ways {

// 我们的算法类不允许产生任何实例

    private QuickSort3Ways(){}

// 递归使用快速排序,对arr[l...r]的范围进行排序

    private static void sort(Comparable[] arr, int l, int r){

// 对于小规模数组, 使用插入排序

        if( r - l <=15 ){

InsertionSort.sort(arr, l, r);

return;

        }

// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot

        swap( arr, l, (int)(Math.random()*(r-l+1)) + l );

        Comparable v = arr[l];

        int lt = l;    // arr[l+1...lt] < v

        int gt = r +1; // arr[gt...r] > v

        int i = l+1;    // arr[lt+1...i) == v

        while( i < gt ){

if( arr[i].compareTo(v) <0 ){

swap( arr, i, lt+1);

                i ++;

                lt ++;

            }

else if( arr[i].compareTo(v) >0 ){

swap( arr, i, gt-1);

                gt --;

            }

else{// arr[i] == v

                i ++;

            }

}

swap( arr, l, lt );

        sort(arr, l, lt-1);

        sort(arr, gt, r);

    }

public static void sort(Comparable[] arr){

int n = arr.length;

        sort(arr, 0, n-1);

    }

private static void swap(Object[] arr, int i, int j) {

Object t = arr[i];

        arr[i] = arr[j];

        arr[j] = t;

    }

// 测试QuickSort3Ways

    public static void main(String[] args) {

// 三路快速排序算法也是一个O(nlogn)复杂度的算法

        // 可以在1秒之内轻松处理100万数量级的数据

        int N =1000000;

        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);

        SortTestHelper.testSort("bobo.algo.QuickSort3Ways", arr);

return;

    }

}