import org.junit.Test;

import java.util.Arrays;

/**
 * Created by wc on 2018/4/28.
 */

public class 快速排序 {

    @Test
    public void test(){
        int[] array={31,21,59,68,12,40};
        sort(array,0,array.length-1);
        System.out.print(Arrays.toString(array));
    }

    /**
     * 數(shù)據(jù)量大用快排
     * 必需是數(shù)組，鏈?zhǔn)浇Y(jié)構(gòu)不要使用快排
     * 重復(fù)元素多，影響性能
     * @param array
     * @param start
     * @param end
     */
    public void sort(int[] array,int start,int end){
        //如果起始大于結(jié)尾就返回
        if(end-start<=0) return ;

        int x=array[start];
        int low=start;
        int high=end;
        boolean direction=true;

        L:
        while(low<high){
            //從右往左
            if(direction){
               for(int i=high;i>low;i--){
                   if(array[i]<=x){
                       array[low++]=array[i];
                       high=i;
                       //換方向
                       direction=!direction;
                       continue L;
                   }
               }
                high=low;
            }else{
                for(int i=low;i<high;i++){
                    if(array[i]>=x){
                        array[high--]=array[i];
                        low=i;
                        direction=!direction;
                        continue L;
                    }
                }
                low=high;
            }
        }
        array[low]=x;
        sort(array,start,low-1);
        sort(array,low+1,end);
    }
}