public static void bubbleSort(int[] arr){
        //中間變量，用來交換數(shù)據(jù)
        int temp = 0;
        //外層循環(huán)
        for (int i = 0 ; i < arr.length - 1 ; i++){
            //內(nèi)層循環(huán)，每次找到最大的數(shù)后放在最后，下次遍歷則會少一次，及arr.length - i - 1
            for(int j = 0; j < arr.length - i - 1; j++){
                //判斷大小
                if(arr[j] > arr[j + 1]){
                    //將兩數(shù)進行交換
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
}

public static void choiceSort(int[] arr){
        //用來記錄最小的數(shù)
        int arrData = 0;
        //記錄最小的數(shù)的下標
        int arrindx = 0;
        //外層循環(huán)，直到 arr.length - 1 即可
        for(int i = 0; i < arr.length - 1; i++){
            //首先把arr[i] 當做最小的數(shù)，并記錄下標
            arrData = arr[i];
            arrindx = i;
            //內(nèi)層循環(huán)，遍歷 i 以后的數(shù)，找到比 arr[i] 還小的數(shù)
            for (int j = i + 1; j < arr.length; j++){
                //找到更小的數(shù)，就進行記錄
                if(arrData > arr[j]){
                    arrData = arr[j];
                    arrindx = j;
                }
            }
            //循環(huán)完畢，說明找到了，最小的數(shù)，與arr[i] 進行交換即可
            arr[arrindx] = arr[i];
            arr[i] = arrData;
        }
}

 public static void insertSort(int[] arr){
        //下標為 0 的數(shù)是確定的，從下標為 1 開始循環(huán)
        for (int i = 1; i < arr.length; i++){
            // 將下標為 i 的數(shù)暫存起來
            int arrData = arr[i];
            //從 i - 1 開始往前循環(huán)
            int arrIndx = i - 1;
            //判斷退出的條件 大于等于0
            while (arrIndx >= 0){
                //如果arrData 大于 下標為arrIndx 的數(shù)，則位置找到，退出循環(huán)
                if (arrData > arr[arrIndx]){
                    break;
                }
                //沒有找到，就將前面的數(shù)往后移
                arr[arrIndx + 1] = arr[arrIndx];
                arrIndx--;
            }
            //找到位置后，就將暫存的數(shù)據(jù)arrData 插入到下標為arrIndx的位置
            arr[arrIndx + 1] = arrData;
        }
    }

    public static void shellSort_exchange(int[] arr){
        //做中間變量，進行數(shù)據(jù)交換
        int temp = 0;
        // g 首先數(shù)組總長除以2， 然后每次除以2
        for(int g = arr.length / 2 ; g > 0 ; g /= 2){
            // i 從 g 的位置開始遍歷
            for(int i = g ; i < arr.length ; i++){
                // j 從 i - g 的位置開始向前遍歷，j 的位置由 j - g 來決定
                for(int j = i - g ; j >= 0 ; j -= g){
                    //判斷 下標(j + g) 和 下標j 位置的數(shù)的大小，然后進行交換
                    if(arr[j + g] < arr[j]){
                        //交換即可
                        temp = arr[j + g];
                        arr[j + g] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
        }
    }

    public static void test1(int[] arr){
        //與前面一樣，開始數(shù)組長度除以2 ， 然后每次除以2
        for(int g = arr.length / 2 ; g > 0 ; g /= 2){
            // i 從 g 位置開始，每次加一
            for(int i = g ; i < arr.length ; i++){
                //定義 j 的位置 為 i
                int j = i ;
                //將 下標為 i 位置的數(shù)暫存起來
                int temp = arr[i];
                //判斷 下標j位置的數(shù) 和 j - g 位置的數(shù)，與前面一樣
                if(arr[j] < arr[j - g] ){
                    //遍歷循環(huán)
                    while(j - g >= 0 && temp < arr[j - g]){
                        //滿足條件，就移位，將前面的數(shù) (下標j - g) 往后移 (下標j)
                        arr[j] = arr[j - g];
                        j -= g;// j 每次 -g
                    }
                }
                //退出循環(huán)或判斷條件后，將暫存的temp (arr[i]) 賦值給 arr[j]
                arr[j] = temp;
            }
        }
    }