快速排序及其优化（JAVA）

1.Java代码实现

public class QuickSort {

    /**
     * 选择一个哨兵节点，将所有小于哨兵节点的元素放到左边，大于哨兵节点的元素放到右边
     * 最后将哨兵节点和小部分中的最右边那个值交换（j），i就处于大部分的最左边
     * @param array 数组元素
     * @param low
     * @param high
     */
    public static void quickSort(Integer[] array,int low,int high){
        if(low>=high){
            return;
        }
        int index = divide(array,low,high);
        quickSort(array,low,index-1);
        quickSort(array,index+1,high);
    }

    private static int divide(Integer[] array,int low,int high){
        int i = low+1, j = high;
        while(i<=j){
            while(i<=j&&array[i]<=array[low]){
                i++;
            }
            while(i<=j&&array[j]>array[low]){
                j--;
            }
            if(i<=j) {
                int k = array[j];
                array[j] = array[i];
                array[i] = k;
            }
        }
        int t = array[low];
        array[low] = array[j];
        array[j] = t;
        return j;
    }
}

2.优化策略（三数选中+插入+聚集）

由于一般哨兵节点都选取最左边或最右边的元素，容易造成时间复杂度为O(N*N)的情况（原数组有序），通过选取三个数（一般可以是最左元素，中间元素，最右元素）中的中间那个数来作为哨兵节点可以减少发生最坏的情况。
在元素个数比较少的情况下，插入排序要由于快排，所以在划分元素足够少的情况下，可以通过插入排序来进行排序。
同时在第一次遍历时，将重复元素聚集在一起，可以减少迭代次数。

public class QuickSort {

    /**
     * @param array 数组元素
     * @param low
     * @param high
     */
    public static void quickSort(Integer[] array,int low,int high){
        if(low>=high){
            return;
        }
        selectPivotMedianOfThree(array,low,high);
        int index = divide(array,low,high);
        int i = index-1,j = index+1;

        //聚集
        int ii = i,jj = j;
        while(ii>=low){
            if(array[index].equals(array[ii])){
                swap(array[ii],array[i]);
                i--;
            }
            ii--;
        }
        while(jj<=high){
            if(array[index].equals(array[jj])){
                swap(array[jj],array[j]);
                j++;
            }
            jj++;
        }

        if(i-low < 10){
            insertSort(array,low,i);
        }else {
            quickSort(array, low, i);
        }
        if(high-j < 10){
            insertSort(array,j,high);
        }else {
            quickSort(array, j, high);
        }
    }

    private static int divide(Integer[] array,int low,int high){
        int i = low+1, j = high;
        while(i<=j){
            while(i<=j&&array[i]<=array[low]){
                i++;
            }
            while(i<=j&&array[j]>=array[low]){
                j--;
            }
            if(i<=j) {
                swap(array[i],array[j]);
            }
        }
        swap(array[low],array[j]);
        return j;
    }

    //三数选中
    private static void selectPivotMedianOfThree(Integer[] array,int low,int high){
        int m = (low+high)/2;
        //实现 array[mid] <= array[low] <= array[high]
        if(array[high] < array[low]){
            swap(array[high],array[low]);
        }
        if(array[high] < array[m]){
            swap(array[high],array[m]);
        }
        if(array[m] > array[low]){
            swap(array[m],array[low]);
        }
    }

    //插入排序
    private static void insertSort(Integer[] array,int low,int high){
        for(int i = low+1; i < high; i++){
            Integer da = array[i];
            int j = i - 1;
            for(; j >= low; j--){
                if(array[j] <= da){
                    break;
                }
                array[j+1] = array[j];
            }
            array[j+1] = da;
        }
    }

    private static void swap(Integer a, Integer b){

        int tem= a;
        Field field= null;
        try {
            field = Integer.class.getDeclaredField("value");
            field.setAccessible(true);
            field.setInt(a, b);
            field.setInt(b, tem);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}