public static void quickSort(int[] arr,int begin,int end){
    //遞歸必須滿足條件：起始值小于終止值
    if(begin<end){
        //這個(gè)方法是確定數(shù)組哨兵在排序后的最終位置下標(biāo)，由于哨兵左邊的數(shù)都小于哨兵，右邊的數(shù)都大于哨兵，所以對(duì)兩邊子數(shù)組進(jìn)行遞歸
        int index = partition(arr,begin,end);
        //對(duì)左邊的子數(shù)組進(jìn)行遞歸 
        quickSort(arr,begin,index-1);
        //對(duì)右邊的數(shù)組進(jìn)行遞歸
        quickSort(arr,index+1,end);
    }
}
public static int partition(int[] arr,int begin,int end){
    //將數(shù)組的最后一個(gè)元素作為哨兵
    int pivot = arr[end];
    //i為起始坐標(biāo)-1
    int i = begin -1;
    //對(duì)數(shù)組進(jìn)行遍歷，j從數(shù)組的第一個(gè)下標(biāo)開(kāi)始，當(dāng)j對(duì)應(yīng)元素小于哨兵時(shí)，i加1，交換i和j對(duì)應(yīng)元素
    for (int j = begin; j < end; j++) {
        //當(dāng)
        if(arr[j]<=pivot){
            i++;
          int tmp = arr[i];
          arr[i]=arr[j];
          arr[j]=tmp;
        }
    }
    //遍歷結(jié)束后，交換arr[i+1]和哨兵的值
    int tmp = arr[i+1];
    arr[i+1]=arr[end]; 
    arr[end]= tmp;
    //i+1就是哨兵最終排序后對(duì)應(yīng)的下標(biāo)
    return i+1;
}

public static int quickSortKMin(int[] arr,int begin,int end,int k){
    //遞歸必須滿足條件：起始值小于等于終止值
    if(begin<=end){
        //這個(gè)方法是確定數(shù)組哨兵在排序后的最終位置下標(biāo)，由于哨兵左邊的數(shù)都小于哨兵，右邊的數(shù)都大于哨兵，所以對(duì)兩邊子數(shù)組進(jìn)行遞歸
        int index = partition(arr,begin,end);
        //如果哨兵的下標(biāo)就等于k-1，那哨兵就是數(shù)組中第k小的值，直接輸出
        if(index==k-1){
            return arr[index];
        }else if(index > k-1){
            //如果k-1小于哨兵的下標(biāo)，說(shuō)明在哨兵左側(cè)，遞歸查找即可
            return quickSortKMin(arr,begin,index-1,k);
        }else{
            //如果k-1大于哨兵的下標(biāo)，說(shuō)明在哨兵右側(cè)，遞歸查找即可
            return quickSortKMin(arr,index+1,end,k);
        }
    }
    return Integer.MIN_VALUE;
}


public static int partition(int[] arr,int begin,int end){
    //將數(shù)組的最后一個(gè)元素作為哨兵
    int pivot = arr[end];
    //i為起始坐標(biāo)-1
    int i = begin -1;
    //對(duì)數(shù)組進(jìn)行遍歷，j從數(shù)組的第一個(gè)下標(biāo)開(kāi)始，當(dāng)j對(duì)應(yīng)元素小于哨兵時(shí)，i加1，交換i和j對(duì)應(yīng)元素
    for (int j = begin; j < end; j++) {
        //當(dāng)
        if(arr[j]<=pivot){
            i++;
          int tmp = arr[i];
          arr[i]=arr[j];
          arr[j]=tmp;
        }
    }
    //遍歷結(jié)束后，交換arr[i+1]和哨兵的值
    int tmp = arr[i+1];
    arr[i+1]=arr[end];
    arr[end]= tmp;
    //i+1就是哨兵最終排序后對(duì)應(yīng)的下標(biāo)
    return i+1;
}