快速排序Quick Sort(其三)-三路快排

快速排序Quick Sort(其三)-三路快排

存在的问题：
之前的排序都没有考虑等于arr[l]的问题，只是把数组分成小于arr[l]和大于arr[l]的两部分，而三路快速排序则是把数组分成小于arr[l],等于arr[l]，大于arr[l]的三部分，这样分隔之后在递归的过程中，对于等于arr[l]的部分我们就不用了管了，只需要递归的对小于arr[l]和大于arr[l]的部分进行同样的快速排序就好了。
解决方法：
Partition具体过程：

 public void quickSort(E[] arr,int n){
        quickSort3(arr,0,-1);
    }
     /**
     * 三路快速排序
     * 将arr[l,...,r]分为<v,==v,>v三部分
     * 之后递归对<v，>v两部分继续进行三路快速排序
     * @param arr
     * @param l
     * @param r
     */
    private void quickSort3(E[] arr, int l ,int r){
        if(l>=r){
            return ;
        }
        //三路快排不是简单地返回一个索引p，对（l- p-1）与（p+1,r）进行递归就好了
        //三路快排中等于v的是一个区间
        //partiton
        int index = (Math.abs(new Random().nextInt())%(r-l+1))+l;
        E t = arr[index];
        arr[index] = arr[l];
        arr[l]= t;

        E 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){
                E temp = arr[i];
                arr[i] = arr[lt+1];
                arr[lt+1] = temp;

                lt ++;
                i++;
            }else if(arr[i].compareTo(v)>0){
                E temp = arr[gt-1];
                arr[gt-1] = arr[i];
                arr[i] = temp;

                gt --;
            }else{
                //arr[i]  == v
                i++;
            }
        }

        E temp = arr[l];
        arr[l] = arr[lt];
        arr[lt] = temp;

        quickSort3(arr,l,lt-1);
        quickSort3(arr,gt,r);
    }

分治算法：分而治之，将原问题分割成同等结构的子问题，之后将子问题逐一解决后，原问题也就得到了解决。快速排序就是典型的分治算法，将原问题分割成同等结构的子问题，之后通过递归算法将子问题逐一解决。