//快速排序法3優于1
//輸入數組(int[] number)作為sort的參數調用sort 即可實現排序（不減序排列）
//或者利用重載的sort方法，輸入參數是(int[] number, 0, number.length-1)
public class 快速排序法1 {
    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 s = number[left]; 
            int i = left; //用時候是++i
            int j = right + 1; //用時候是--j，

            while(true) { 
                // 向右找 ，直到找到大于等于s
                while(i + 1 < number.length && number[++i] < s) ;  
                // 向左找 ，直到找到小于等于s
                while(j -1 > -1 && number[--j] > s) ;  
                if(i >= j) 
                    break; 
                swap(number, i, j); 
            } 

            number[left] = number[j]; 
            number[j] = s; 

            sort(number, left, j-1);   // 對左邊進行遞迴 
            sort(number, j+1, right);  // 對右邊進行遞迴 
        }
    }
    
    //在數組number中交換下標為i、j的元素，其他元素保存不變
    private static void swap(int[] number, int i, int j) {
        int t; 
        t = number[i]; 
        number[i] = number[j]; 
        number[j] = t;
    }
}