package leetcode;

public class Singleton {
    public static void sort(int[] array,int low,int high){
        int i,j;
        int temp;
        i = low;
        j = high;
        if (i>j)
            return;
        int index = array[0];
        while (i<j){
            while (array[j]>=index && i<j)
                //从后往前比较
                j--;
            if (i<j){
                //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
                temp = array[i];
                array[i++] = array[j];
                array[j] = temp;
            }
            while (array[i]<index && i<j)
                //从前往后比较
                i++;
            if (i<j){
                //如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
                temp = array[i];
                array[i] = array[j];
                array[j--] = temp;
            }
        }
        sort(array,low,i-1);
        sort(array,i+1,high);
    }
    public static void quickSort(int[] array){
        sort(array,0,array.length-1);
    }
    public static void main(String args[]) {
        int array[] = {5,4,9,8,7,6,0,1,3,2};
        quickSort(array);
        for (int i=0;i<array.length;i++){
            System.out.println(array[i]);
        }
    }
}