/*  two known area:

* [0, leftIndex) < pivotValue; (rightIndex, right] >= pivotValue *  [leftIndex, rightIndex] is the unknown area * */ public class QuickSort {
        static Random random = new Random() ;     public static void main(String[] args){
            int[] array = {1,9,8,5,3};         sortIntegers(array);         print(array);     }     private static void sortIntegers(int[] arr){
            if (arr == null || arr.length ==0) return;         quickSort(arr, 0 , arr.length-1);     }     private static void quickSort(int[] array, int left, int right) {
            if (left>=right) return;         int pivotPos = partition(array, left, right);         quickSort(array, left, pivotPos-1);         quickSort(array, pivotPos +1 , right);     } //leftIndex is the 1st pos value >= pivotValue     private static int partition(int[] array, int left, int right) {
            int pivotIndex = left + random.nextInt(right - left + 1 ) ;         int pivotValue = array[pivotIndex];         //change pivot value to the right         swap(array,pivotIndex,right);         int leftIndex = left;         int rightIndex = right-1;//since the pivot on right no need to be included         while(leftIndex<=rightIndex){
                if (array[leftIndex]
     
      =pivotValue){
                    rightIndex--;             } else {
                    //same                 //swap(array, leftIndex++,rightIndex--);                 swap(array, leftIndex,rightIndex);                 leftIndex++;                 rightIndex--;             }         }         //change pivot from the right to the correct position         swap(array,leftIndex,right);         return leftIndex ;     }     private static void swap(int[] array, int pivotIndex, int right) {
            int temp = array[pivotIndex] ;         array[pivotIndex] = array[right];         array[right] = temp ;     }     public static void print(int[] array){
            for (int i = 0; i < array.length; i++) {
                System.out.println(array[i]);         }     } }
     

 时间复杂度， 空间复杂度 

average: nlogn : logn 层 每层 n 次排序

          n

   n/2     n/2 

 n/4 n/4   n/4  n/4 

worst: 每次取最大或者最小值