package com.imooc.oa.array;
import java.util.Random;
public class QuickSort {
    private QuickSort(){
    }
    public static int[] generateRandomArray(int n){
        if(n<0 || n>100000000) {
            System.out.println("超出范围");
            int[] arr ={-1};
            return arr;
        }
        int [] arr= new int[n];
        Random random = new Random();
        for(int i=0; i<n; i++){
            arr[i]=random.nextInt(n*3);
        }
        return arr;
    }
    private static void sort(int[] arr, int left,int right){
          if(left >= right) return;
          int point = partition(arr, left, right);
          sort(arr, left, point-1);
          sort(arr, point+1, right);
    }
    public static int partition(int[] arr, int left, int right){
        int j=left;
        int i;
        for( i = j+1; i<=right; i++){
            if(arr[i]<arr[j]){
                j++;
                swap(arr, i , j);
            }
        }
        swap(arr,left,j);
        return j;
    }
    public static void swap(int[] arr,int a, int b){
          int temp = arr[a];
          arr[a] = arr[b];
          arr[b] = temp;
    }
    public static void main(String[] args) {
        int[] a = QuickSort.generateRandomArray(20);
        for (int i=0; i<a.length; i++){
            System.out.print(a[i] + ",");
        }
        System.out.println();
        sort(a, 0, 19);
        for (int i=0; i<a.length; i++){
            System.out.print(a[i] + ",");
        }
    }
}