//快速排序 通过测试

public class QuickSortTest2 {

    public static void quickSort(int[] data,int low,int high){   //此处O(logn)

        int index;

        if(low<high) {

         index=partition(data,low,high);

            quickSort(data,low,index-1);

            quickSort(data,index+1,high);

        }

    } 

    public static int partition(int[] data, int i, int j) { // O(n)

            int k=data[i];

            while(i<j){

                while(i<j&&data[j]>=k)

                    j--;

                if(i<j)

                    data[i++]=data[j];

                while(i<j&&data[i]<=k)

                    i++;

                if(i<j)

                    data[j--]=data[i];

            }

            data[i]=k;

            return i;

   }

//-----------------------------------------------------------------------------

    public static void main (String args[]){

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

        quickSort(x,0,x.length-1);

        for(int i=0;i<x.length;i++){

            System.out.println(x[i]);

        }

    }

}

//快速排序 通过测试

public class QuickSortTest_ali {

     void quickSort(int[] data,int length){

        if(length<=1) return;

        int start=0;

        int end=length-1;

        int pivot=data[0];

        while(start<end){

            for(;start<end;end--){

                if(data[end]<pivot){

                    data[start++]=data[end];

                    break;

                }

            }

            for(;start<end;start++){

                if(data[start]>pivot){

                    data[end--]=data[start];

                    break;

                }

            }

        }

        data[start]=pivot;

        quickSort(data,start);

        quickSort(data+start+1,length-start-1);

    }

//-----------------------------------------------------------------------------

    public static void main (String args[]){

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

        quickSort(data,0,data.length-1);

        for(int i=0;i<x.length;i++){

            System.out.println(x[i]);

        }

    }

}