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

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


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