/**

 *

 */

package com.cherish.SortingAlgorithm;

/**

 * @author acer

 *

 */

public class Chapter_6_QuickSorting extends ArrayBase{

    /**

     *

     */

    public Chapter_6_QuickSorting() {

        // TODO 自动生成的构造函数存根

    }

    /**

     * @param args

     */

    public static void main(String[] args) {

        // TODO 自动生成的方法存根

        int[] array = new int[] {3,4,7,9,2,5,1,8,6};

        quickSorting(array,0,array.length-1);

        printArray(array);

    }

    /*

     * 通过一趟排序将要排序的数据分割成独立的两部分，

     * 其中一部分的所有数据都比另外一部分的所有数据都要小，

     * 然后再按此方法对这两部分数据分别进行快速排序，

     * 整个排序过程可以递归进行，以此达到整个数据变成有序序列。

     * */

    public static void quickSorting(int[] array,int low,int high)

    {

        if(low < high)

        {

            //获取基准点

            int middle = getMiddle(array,low,high);

            quickSorting(array,low,middle-1);

            quickSorting(array,middle+1,high);

        }

    }

    //对每个分部数组进行排序，并给出下一轮的数组切分点

    public static int getMiddle(int[] list,int low,int high)

    {

        //数组的第一个数为基准元素

        int temp = list[low];

        while(low<high)

        {

            while(low<high && list[high]>temp)

            {

                high--; //从后向前找比基准小的数

            }

            //把比基准小的数移到低端

            list[low] = list[high];

            while(low<high && list[low] < temp)

            {

                low++; //从前向后找比基准大的数

            }

            //把比基准大的数移到高端

            list[high] = list[low];

        }

        list[low] = temp;

        return low;

    }

}