排序5：快速排序（递归方式）

/**
 * @desc: 快速排序
 * @author: 毛会懂
 * @create: 2020-12-24 14:01:00
 **/
public class Fast {

    public static void sort(Comparable[] arr){
        sort(arr,0,arr.length-1);
    }

    private static void sort(Comparable[] arr,int low,int high){
        if(low >= high){
            return;
        }
        int index = partition(arr,low,high);
        sort(arr,low,index-1);
        sort(arr,index+1,high);
    }

    private static int partition(Comparable[] arr,int low,int high){
        Comparable refer = arr[low]; //基准值
        int left = low;
        int right = high +1;
        while (left < right){
            while (less(refer,arr[--right])){ //找右边比基准值小的数
                if(left == right){
                    break;
                }
            }
            while (less(arr[++left],refer)){ //找左边比基准值大的数
                if(left >= right){//在left == right的情况下， ++left 后，left> right 了
                    break;
                }
            }
            if(left < right) { //左边的比基准值大，右边的比基准值小，则交换
                exchange(arr, left, right);
            }else{
                break;
            }
        }
        //右下标已经移到基准位置了，不用交换
        if(low != right) {
            exchange(arr, low, right);
        }
        return right;
    }

    private static Boolean less(Comparable o1,Comparable o2){
        return o1.compareTo(o2) < 0;
    }

    private static void exchange(Comparable[] arr,int i,int j){
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

    //快速排序（Person的定义见之前的文章）
    public static void main(String[] args) {
//        Integer[] arr = {10,8,20,30,5,7,4,12,40,30,1,2,4,3,100,5,32,45,23,66,45,7,55,79,6};
//        //Integer[] arr = {5,4,7,8,3};
//        Fast.sort(arr);
//        Arrays.asList(arr).forEach(System.out::println);

        Person[] persions = {new Person("b", 11), new Person("a", 10), new Person("c", 12), new Person("b", 111),
                new Person("a", 5), new Person("c", 4)};
        Fast.sort(persions);
        for (Person person : persions) {
            System.out.println(person);
        }
    }


附录：网上的一种快排方式
//快速排序
public static void main(String[] args) {
    int[] arr = {10,8,20,30,5,7,4,12,40,30,1,2,4,3,100,5,32,45,23,66,45,7,55,79,6};
    //Integer[] arr = {5,4,7,8,3};
    quickSort_2(arr,0,arr.length-1);
    for (int i : arr) {
        System.out.println(i);
    }
}

public static void quickSort_2(int[] data, int start, int end) {
    if (data == null || start >= end) return;
    int i = start, j = end;
    int pivotKey = data[start];
    while (i < j) {
        while (i < j && data[j] >= pivotKey) j--;
        if (i < j) data[i++] = data[j];
        while (i < j && data[i] <= pivotKey) i++;
        if (i < j) data[j--] = data[i];
    }
    data[i] = pivotKey;
    quickSort_2(data, start, i - 1);
    quickSort_2(data, i + 1, end);
}