快速排序法3.java

输入数组作为sort的参数调用sort 即可实现排序（不减序排列） //或者利用重载的方法

//快速排序法3优于1
//输入数组作为sort的参数调用sort 即可实现排序（不减序排列）
//或者利用重载的方法，参数是(int[] number, 0, number.length-1)
public class 快速排序法3 {
    public static void sort(int[] number) {
        sort(number, 0, number.length-1);
    }
    //重载
    private static void sort(int[] number, 
                             int left, int right) {
        if(left < right) { 
            int q = partition(number, left, right); 
            sort(number, left, q-1); 
            sort(number, q+1, right); 
        } 

    }

    private static int partition(int number[], 
                                 int left, int right) {  

        int s = number[right]; 
        int i = left - 1; 

        for(int j = left; j < right; j++) { 
            if(number[j] <= s) { 
                i++; 
                swap(number, i, j); 
            } 
        } 

        swap(number, i+1, right); 
        
        return i+1; 
    } 

    private static void swap(int[] number, int i, int j) {
        int t; 
        t = number[i]; 
        number[i] = number[j]; 
        number[j] = t;
    }
}