java算法之快速排序（递归方式）

/** 
 * @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); 
}