美文网首页
快速排序

快速排序

作者: codezwc | 来源:发表于2018-04-28 21:51 被阅读0次
    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));
        }
    
        /**
         * 数据量大用快排
         * 必需是数组,链式结构不要使用快排
         * 重复元素多,影响性能
         * @param array
         * @param start
         * @param end
         */
        public void sort(int[] array,int start,int end){
            //如果起始大于结尾就返回
            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);
        }
    }
    

    相关文章

      网友评论

          本文标题:快速排序

          本文链接:https://www.haomeiwen.com/subject/nypnlftx.html