快速排序

思想：采用分治法。对于有N个元素的数组，任意选择一个元素作为pivot基准元素，然后把比基准元素小的元素划分到左边，比基准元素大的元素划分到右边。此时如果左边和右边的元素完成排序，则整个数组的排序就变成左边的元素加基准元素加右边元素。

假设开始的时候选择最后一个元素为基准元素，遍历start到end-1，如果比基准元素小，就放到storeIndex位置，storeIndex初始=start,有交换则storeIndex++;全部遍历结束，storeIndex指向的位置即为基准元素的最终位置，故交换基准元素和storeIndex所在位置的元素。

    public void quickSort(int a[]) {
        quickSort(a, 0, a.length - 1);
    }
    public void quickSort(int a[], int start, int end) {
        if (start < end) {
            int pivot = partition(a, start, end);
            quickSort(a, start, pivot - 1);
            quickSort(a, pivot + 1, end);
        }

    }

    /**
     * @param a
     * @param i
     * @param j
     * @return <p>
     *         Description:
     *         </p>
     */
    private int partition(int[] a, int start, int end) {
        int pivotData = a[end];
        int storeIndex = start;
        for (int j = start; j < end; j++) {
            if (a[j] <= pivotData) {
                swap(a, j, storeIndex);
                storeIndex++;
            }
        }
        swap(a, end, storeIndex);
        return storeIndex;
    }

快速排序的时间复杂度是O(nlogn),快速排序的pivot的随机性，所以快速排序有点类似于一颗平衡二叉树，树的每一层都要遍历n个元素，树的高度是logn。所以总共的时间复杂度是O(nlogn),递归也有时间复杂度，但远小于O(nlogn)
下面给出随机选择一个pivot的算法

/**
     * 
     * @param a
     * @param left
     * @param right
     * @return
     *<p>Description:随机选择一个pivot </p>
     */
    private int partitionRandom(int[] a, int left, int right) {

        Random random=new Random();
        int pivotIndex=random.nextInt(right-left)+left;
        int pivotData=a[pivotIndex];
        swap(a,pivotIndex,right);
        int startIndex=left;
        for(int i=left;i<right;i++){
            if(a[i]<=pivotData){
                swap(a, i, startIndex);
                startIndex++;
            }   
            }
        swap(a, right, startIndex);
        System.out.println("pivot:"+startIndex);
        return startIndex;
    }