快速排序(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]);
    }
}

本站运行时间: 0天 0小时 00分00秒

Copyright © 2020 过去的,未来的

Powered by Halo • Theme by Subtle Galaxy • REFERENCE FROM 寒山

Back to the top