package com.tju.sort;

/**
 * Created by xiangyang.laixiang on 2016/8/2.
 */
public class QuickSort {

    /**
     * 快速排序
     * 挖坑填数+分治思路
     * 首先寻找一个基准点，将其值c缓存下来
     * 以基准点为标准左右挪移，将所有大于基准点的数挪到右边，小于基准点的数
     * 挪到左边，首先在起始点a挖坑，然后在右面寻找第一个小于基准点的数b填入起始点的坑，此时相当于又
     * 在b处挖了一个新坑
     * 接着从左边找到大于基准点的数d填入b的坑，此时又相当于在d处挖了一个新坑
     * 最后将我们刚开始缓存下来的值c填入d
     * 此时坑没有了，操作也完成了
     */
    public static void quickSort(int a[], int from,int to) {
        if(from<to)
        {
            //寻找中值点
            int middle = getMiddle(a,from,to);
            quickSort(a,from,middle);
            quickSort(a,middle+1,to);
        }
    }

    public static int getMiddle(int a[], int low, int high)
    {
        //缓存值
        int key=a[low];
        while(low<high)
        {
            //从右边找小于起始值的数
            while(low<high&&a[high]>=key)
            {
                //找到
                high--;
            }
            //填坑
            a[low]=a[high];
            while(low<high&&a[low]<=key)
            {
                //找到
                low++;
            }
            //填坑
            a[high]=a[low];
        }
        //填坑
        a[low]=key;
        return low;
    }

    public static void main(String[] args)
    {
        int a[]={6,1,2,7,8,9,3,6};
        quickSort(a,0,a.length-1);
        for (int value : a)
        {
            System.out.println(value);
        }
    }
}