package 基础算法;

/**
 * @author rd-yyx
 * @version 1.0
 * @date 2020/5/19 10:59 上午
 */
public class QuickSort {
    static void quickSort(int[] a, int n){
        quick_sort_c(a,0,n-1);
        return;
    }
    static void quick_sort_c(int []a,int p ,int r){
        if(p > r){
            return ;
        }
        int q =partition(a,p,r);
        quick_sort_c(a, p ,q-1);
        quick_sort_c(a,q+1,r);
        return;
    }
    static int partition(int []a, int p , int r){

        int flag = a[r];
        int swap;
        int i = p;
        for(int j = p ; j <= r-1 ; j++){
            if(a[j] < flag ){
                swap = a[j];
                a[j] = a[i];
                a[i] = swap;
                i++;
            }
        }
        swap = a[i];
        a[i] = a[r];
        a[r] = swap;

        return i;
    }

    public static void main(String[] args) {
        int a[] = {4,8,5,7,1,0,9,6};//实验数据
        quickSort(a,8);
        for (int i : a) {
            System.out.print(i+" ");
        }
    }
}