手写快速排序

哎 边界有点绕呢

package 算法;

public class 快速排序 {


    public static void quickSort(int[] arr) {
        if (arr == null||arr.length==1) {
            return;
        }
        proscss(arr,0,arr.length-1);
    }

    /**
     * 快速排序
     * @param arr
     * @param l
     * @param r
     */
    public static void proscss(int[] arr,int l ,int r){
        //跳出机制
        if (l >= r) {
            return;
        }
        //排序当前 分为 小于 等于 大与 并返回对应下标志
        int a[] =  sort1(arr,l,r);
        //递归继续排序小于
        proscss(arr,l,a[0]);
        //递归继续排序大与
        proscss(arr,a[1],r);
    }

    /**
     * 具体的拆分,实现 按照R为标杆,p1左边是小数 p1-p2中间是相等数 p2-r是大与的数
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int[] sort1(int[] arr, int l, int r) {
        System.out.println("l="+l+"r="+r);
        //跳出
        if(l>=r){
            return new int[]{l,r};
        }
        //如果是2个就直接排序
        if(r-l==1){
            if (arr[l] > arr[r]) {
                swap(arr,l,r);
            }
            return new int[]{l,r};
        }
        int p1 = l;
        int p2 = r-1;//这里从r-1开始算 r作为中间数
        int i = l;
        //i 是判断的,直到p2 p2 右边是大与R的数 是已经判断交换过的
        while (i<=p2){
            //如果i大与于r 就放到大与于堆里
            if (arr[i]>arr[r] ){
                //i与 p2 交换  p2 --
                swap(arr,i,p2);
                p2--;
                continue;
            }
            //如果i小于r 放到小于的堆里
            if (arr[i]<arr[r] ){
                //交换第i个与p1  p1++
                swap(arr,i,p1);
                p1++;
                i++;
                continue;
            }
            //如果i等于r 就放到等于堆里
            if (arr[i]==arr[r] ){
                i++;
                continue;
            }


        }
        //将r放到中间
        swap(arr,p2+1,r);
        p2++;
        int[] rt = new int[2];
        rt[0]=p1-1;
        rt[1]=p2+1;
        return rt;
    }
    public static void swap(int[] arr,int i,int j){
        if ( i== j) {
            return;
        }
        System.out.println("i="+i+"j="+j);
        arr[i] = arr[i]^arr[j];
        arr[j] = arr[i]^arr[j];
        arr[i] = arr[i]^arr[j];
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1,6,5,2,7,5,3,8,4,5};
        quickSort(arr);
        System.out.println(arr.toString());
    }
}

上一篇:从后往前替换空格


下一篇:DIY桌面机械臂__机械结构设计_p2