编辑代码

public class Main6 {
    public static void main(String[] args) {
        //JSRUN引擎2.0，支持多达30种语言在线运行，全仿真在线交互输入输出。
        System.out.println("Hello world!   - java.jsrun.net ");
        int[] a={5,3,21,21,32,10,34,53,2,35,74};
        int[] b={10,9,8,7,6,5,4,3,2,1};
        int[] c={1,2,3,4,5,6,7,8,9,10};
        int[] d={0,0,0,0};
        int[] e={1};
        int[] f={2,1};
        quickSort(a,0,a.length);
        display(a);
        quickSort(b,0,b.length);
        display(b);
        quickSort(c,0,c.length);
        display(c);
        quickSort(d,0,d.length);
        display(d);
        quickSort(e,0,e.length);
        display(e);
        quickSort(f,0,f.length);
        display(f);
    }
    public static void display(int[] array){
        for (int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
    //算法
    public static void quickSort(int[] array, int arrStart, int arrEnd){
//        System.out.print("原始："+"start:"+arrStart+" arrEnd:"+arrEnd+" |||| ");
        int arrLen = arrEnd - arrStart;
        if(arrLen <= 1){
            return;
        }
//        display(array);
        int pivotPos = findPivot(array,arrStart,arrEnd);
        int point = partition(array,arrStart,arrEnd,pivotPos);
        quickSort(array,arrStart,point);
        quickSort(array,point+1,arrEnd);
    }
    //找点(头-中-尾--》取中间大小)
    public static int findPivot(int[] array, int arrStart, int arrEnd){
        int[] one ={array[arrStart],array[(arrEnd-arrStart)/2],array[arrEnd-1]};
        int[] index={arrStart,(arrEnd-arrStart)/2,array[arrEnd-1]};
        for(int i=0;i<2;i++){
            for (int j=0;j<2;j++){
                if(one[i]>one[i+1]){
                    int temp=one[i];
                    one[i]=one[i+1];
                    one[i+1]=temp;
                    temp = index[i];
                    index[i] = index[i+1];
                    index[i+1] = temp;
                }
            }
        }
        return index[1];
    }
    //分治--数组内部交换（原地工作）
    public static int partition(int[] array, int arrStart, int arrEnd , int pivotPos){
        for(int i=arrStart;i<arrEnd;i++){
            if(array[pivotPos]==array[i]){continue;}
            else if(array[pivotPos]>array[i]){
                if(i<pivotPos){
                    continue;
                }
                else {
                    int temp=array[i];
                    for(int j=i;j>pivotPos;j--){
                        array[j]=array[j-1];
                    }
                    array[pivotPos]=temp;
                    pivotPos++;
                    i--;
                }
            }
            //array[pivotPos]<array[i]
            else {
                if(i>pivotPos){
                    continue;
                }
                else{
                    int temp=array[i];
                    for(int j=i;j<pivotPos;j++){
                        array[j]=array[j+1];
                    }
                    array[pivotPos]=temp;
                    pivotPos--;
                    i--;
                }
            }
//            display(array);
//            System.out.println(pivotPos+"--"+i+"次数");
        }
//        System.out.println("-==============================-");
        return pivotPos;
    }
}