3.1.0 快速排序

quicksort

public class QuickSort {
    
    public static void sort(int[] arr) {
        if(arr == null || arr.length < 2) return;
        quicksort(arr,0, arr.length -1);
    }

    public static void quicksort(int[] arr, int left, int right) {
        if(left < right) {
            int[] pos = partition(arr, left, right);
            quicksort(arr,left,pos[0]-1);
            quicksort(arr, pos[1]+1,right);
        }
        
    }
    //return array[] 2 with leftboundary and rightboundary
    public static int[] partition(int[] arr, int left, int right) {
        if(left == right) return new int[] {left,left};
        int less = left -1;
        int more = right;
        int target = arr[right];
        
        while(left < more) {
            if(arr[left] < target) {
                swap(arr, ++less, left++);
            }else if(arr[left] > target) {
                swap(arr,--more,left);
            }else {
                left++;
            }
        }
        swap(arr, more,right);
        return new int[] {less+1, more};
    }
    
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    
    public static void main(String[] args) {
        int [] arr = {4,3,2,1};
        sort(arr);
        for(int i=0; i < arr.length;i++) {
            System.out.println(arr[i]);
        }
    }
}