排序：快速排序

快速排序是一种交换排序，他是稳定的排序,时间复杂度是nlogn,因为每次partition需要n个时间,共分为logn次.所以整体时间复杂度是nlogn.
它的核心是：找到一个索引，把小于它的数值放在它的左边，大于它的放在右边.然后依次将左边的数组和右边的数组进行递归.
这个索引最好是一个中位值,保证左右两遍的长度差值不大,否则会导致整体时间复杂度变高.
Ps:左右两边进行交换的时候不能使用swap,这样会把mid值弄丢.因为为了避免出现相等情况的死循环,在遇到相等数值的情况下,会继续跳跃不能进行交换.
所以采用直接赋值的方案,这种方法可以实现解决这个问题.
至于为什么可以解决这个问题,可以用数学方法证明出来.(我还没有领会!!)

package Sort;

/**
 * Created by Hammy on 2018/3/1.
 */
public class QuickSort
{
    public QuickSort(){};

    public static void sort(int[] array){
        quickSort(array,0,array.length-1);
    }
    private static void quickSort(int[] array,int left,int right){
        if(left >= right)
            return;

        int index = partition(array,left,right);
        quickSort(array,left,index-1);
        quickSort(array,index+1,right);
    }

    private static int partition(int[] array, int left, int right){
        int mid = getMid(array, left, right);
        int temp = array[mid];

        while(left<right){
            while(right>left&&array[right]>=temp)
                right--;

            array[left]=array[right];

            while(left<right&&array[left]<=temp)
                left++;

            array[right]=array[left];
        }

        array[left]=temp;
        return left;
    }

    public static int getMid(int[] array,int left,int right){
        int mid = (left+right)>>1;

        if(array[left]>array[right]){
            Util.swap(array,left,right);
        }
        if(array[mid]>array[right]){
            Util.swap(array,mid,right);
        }
        if(array[mid]>array[left]){
            Util.swap(array,left,mid);
        }
        return left;
    }

}