William

/**
 * 快速排序
 * @author xiaomi
 * 2012.4.2
 */
public class QuickSort {
    public static void main(String[] args) throws IOException{
        String s = InputString.getString();
        String[] str = s.split(" ");
        int[] a = new int[str.length+1];
        for(int i = 0;i < str.length;i++){
            a[i+1] = Integer.parseInt(str[i]);
        }
        quickSort(a,1,a.length-1);
        for(int i = 1;i < a.length;i++){
            System.out.print(a[i]+" ");
        }
    }
   
    public static void quickSort(int[] a,int low,int high){
        if(low < high){
            int pivot = partion_1(a, low, high);
            quickSort(a, low, pivot-1);
            quickSort(a, pivot+1, high);
        }
    }
    //method1   
    public static int partion_1(int[] a,int low,int high){
        a[0] = a[low];
        int pivot = a[low];
        while(low<high){
            while(low < high && a[high] >= pivot){
                high--;
            }
            a[low] = a[high];
            while(low < high && a[low] <= pivot){
                low++;
            }
            a[high] = a[low];
        }
        a[low] = a[0];
        return low;
    }
    //method2   
    public static int partion_2(int[] a,int low,int high){
        int pivot = a[low];
        while(low<high){
            while(low < high && a[high] >= pivot){
                high--;
            }
            while(low < high && a[low] < pivot){//不能都加‘=’号，否则可能high跑到low前面
                low++;
            }
            int temp = a[high];
            a[high] = a[low];
            a[low] = temp;
        }
        return low;
    }
}