시작, 중간, 마지막을 기준으로 하는 귀속 빠른 배열 실현

구분된 첫 번째 요소를 기준값으로 하는 빠른 배열:

private static void quickSort(int a[],int l,int r){
        if(lint i=l,j=r,index=a[l];
            while(iwhile(i=index){
                    j--;
                }
                if(iwhile(iif(i1);
            quickSort(a,i+1,r);
        }
    }

구분된 마지막 요소를 기준으로 하는 빠른 정렬:

private static void quickSort1(int a[],int l,int r){
        if(lint i=l,j=r,index=a[r];
            while(iwhile(iif(iwhile(i=index){
                    j--;
                }
                if(i1);
            quickSort(a,i+1,r);
        }
    }

중위수를 기준으로 바꾸려고 했습니다.

private static void quickSort2(int a[],int l,int r){
        if(lint i = l, j = r, mid = (l+r)/2;
            int index = a[mid];
            while(i < j) {
                while(i < j && a[j] > index) {
                    j--;
                }
                while(i < j && a[i] < index) {
                    i++;
                }
                if(i < j) {
                    int tmp = a[i];
                    a[i] = a[j];
                    a[j] = tmp;
                }
            }
            System.out.println(i+" "+j+" "+mid);
            quickSort2(a,l,i - 1);
            quickSort2(a, i + 1, r);
        }

문제는 수조 중 어떤 중복 원소가 있으면 사순환에 빠진다는 것이다
마지막 요소를 기준으로 하는 코드를 사용하여 중간 수와 마지막 수만 교환하면 된다는 생각을 다시 한 번 바꿀 수 있습니다.

    private static void quickSort2(int a[],int l,int r){
        if(l2);
            int index = a[r];
            int p = l;
            for(int i = l; i < r; i++) {
                if(a[i] < index) {
                    swap(a, p, i);
                    p++;
                }
            }
            swap(a, p, r);
            quickSort2(a,l,p - 1);
            quickSort2(a, p + 1, r);
        }
    }
    private static void swap(int a[], int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

무작위 수를 기준으로 해도 마찬가지다.

private static void quickSort2(int a[],int l,int r){
        if(ldouble ran = Math.random();
            swap(a, r, (int)(ran*(r - l) + l));
            int index = a[r];
            int p = l;
            for(int i = l; i < r; i++) {
                if(a[i] < index) {
                    swap(a, p, i);
                    p++;
                }
            }
            swap(a, p, r);
            quickSort2(a,l,p - 1);
            quickSort2(a, p + 1, r);
        }
    }
    private static void swap(int a[], int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

일반적으로 반복은 다음과 같은 코드를 사용하여 스택으로 시뮬레이션할 수 있습니다.

class range {
    int l;
    int r;
    public range(int l, int r) {
        this.l = l;
        this.r = r;
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int a[]=new int[n];
        for(int i=0;i stk = new Stack<>();
        stk.push(new range(0, n - 1));
        while(!stk.isEmpty()) {
            range ran = stk.pop();
            int l = ran.l;
            int r = ran.r;
            int p = quick(a, l, r);
            if(p != -1) {
                stk.push(new range(l, p - 1));
                stk.push(new range(p + 1, r));
            }
        }

        for(int i=0;i1;i++){
            System.out.print(a[i]+" ");
        }System.out.println(a[n-1]);
    }

    public static int quick(int a[], int l, int r) {
        if(ldouble ran = Math.random();
            swap(a, r, (int)(ran*(r - l) + l));
            int index = a[r];
            int p = l;
            for(int i = l; i < r; i++) {
                if(a[i] < index) {
                    swap(a, p, i);
                    p++;
                }
            }
            swap(a, p, r);
            return p;
        }
        return -1;
    }
    private static void swap(int a[], int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

좀 복잡해 보이지만 본질은 변하지 않았다