快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序原理图

public static intpartition(int[]array,intlo,int hi){

        //固定的切分方式intkey=array[lo];

        while(lo

            while(array[hi]>=key&&hi>lo){//从后半部分向前扫描

                hi--;

            }

            array[lo]=array[hi];

            while(array[lo]<=key&&hi>lo){从前半部分向后扫描

                lo++;

            }

            array[hi]=array[lo];

        }

        array[hi]=key;

        return hi;

    }

    publicstaticvoidsort(int[] array,intlo ,int hi){

        if(lo>=hi){

            return ;

        }

        intindex=partition(array,lo,hi);

        sort(array,lo,index-1);

        sort(array,index+1,hi);

    }

TODO:时间复杂度，空间复杂度，快速排序的优化