快速排序(1):单向快排

单向快排

public class TemplateProduceApplicationTests {
    public static void main(String[] args) {
        Integer[] arr= getRandomArr(10,10,20,false);
        printArr(arr);
        OneWayQuick(arr,0,arr.length-1);
        System.out.println("");
        printArr(arr);
       /*Integer arr[]=new Integer[]{1,2,3};
        swapTwo(arr,0,2);
        printArr(arr);*/

    }
    public static void printArr(Integer arr[]){
        for (Integer ele:arr) {
            System.out.print(ele+" ");
        }
    }
    @Test
    public void contextLoads() {
        Integer[] arr= getRandomArr(10,10,20,false);
        System.out.println(arr);
        OneWayQuick(arr,0,arr.length-1);
        System.out.println(arr);
    }
    public static void OneWayQuick(Integer arr[],int l,int r){
        if(l<r){
            int middle=partition(arr,l,r);
            OneWayQuick(arr,l,middle-1);
            OneWayQuick(arr,middle+1,r);
        }
    }
    //一次排序结果 找到第一个元素的位置分为两部分
    public static int partition(Integer arr[],int l,int r){
        int priot=arr[l];
        int left=l+1;
        int right=r;
        while (left<=right){
            if(arr[left]<=priot){
                left++;
            }
            else{
                swapTwo(arr,left,right);
                right--;
            }

        }
        swapTwo(arr,l,right);
        return right;
    }

    /**
     * 交换两个数
     * @param arr
     * @param first
     * @param end
     */
    public  static void swapTwo(Integer arr[],int first,int end){
        //防止有可能存在两个相同的数交换结果为0
        if(first == end)
            return;
        arr[first]=arr[first]^arr[end];
        arr[end]=arr[first]^arr[end];
        arr[first]=arr[first]^arr[end];
     /*  int temp=arr[first];
       arr[first]=arr[end];
        arr[end]=temp;*/
    }

    /**
     * 获取一个随机数组
     * @param length
     * @param min
     * @param max
     * @param isRepeat
     * @return
     */
    public static Integer[]  getRandomArr(int length,int min,int max,boolean isRepeat){
        Collection<Integer> arr=isRepeat?new ArrayList<Integer>():new HashSet<Integer>();
        Random rand=new Random();
        while(arr.size()!=length){
            arr.add(rand.nextInt(max-min)+min);
        }
        return arr.toArray(new Integer[0]);
    }
}

更新时间:2019-12-01 04:22:53

本文由 过去的,未来的 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.fengpt.cn/archives/rbb
最后更新:2019-12-01 04:22:53

评论

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×