package com.qunar.hotel.qta.order.core.common;

/**
 * Created by ling.yu on 2015/10/12.
 */
public class QS {

    public static void main(String[] agrs){
        int[]a =new int []{5,3,4,7,6,2,1,8};
        for(int i=0;i<a.length;i++)
            System.out.print(a[i]+"  ");
        qsort(a, 0, a.length-1);
        System.out.println();
        for(int i=0;i<a.length;i++)
            System.out.print(a[i] + "  ");


    }
    public static void qsort(int[]a,int i ,int j )
    {
        if (i<j){
            int token=partition(a,i,j);
                qsort(a, i, token - 1);
                qsort(a, token + 1, j);

        }
    }
    public static int partition(int[] a ,int i,int j){
        int token=a[i];
        while (i<j){
            while (token <a[j])
            {
                --j;
            }
            if (i<j) {
                a[i] = a[j];
                i++;
            }
            while(token>a[i])
            {
                ++i;
            }
            if (i<j) {
                a[j] = a[i];
                j--;
            }
        }
        a[i]=token;
        return i;
    }
}