public static void bubbleSort(int[] arr){
        int temp = 0;
        //標識變量，表示是否進行過交換
        boolean flag = false;
        //時間復雜度O(n^2)
        for (int i = 0; i < arr.length - 1; i++) { //一共要排序幾次
            for (int j = 0; j < arr.length - 1 - i; j++) {//每次排序需要比較的次數(shù)
                if (arr[j] > arr[j + 1]){
                    flag = true;
                    temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
            if (flag){//出現(xiàn)過交換，重置flag
                flag = false;
            }else//在上一趟排序中，一次交換也沒有發(fā)生過
                break;
        }
    }

public static void selectSort(int[]arr){
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            int min = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                if (min > arr[j]){
                    minIndex = j;
                    min = arr[j];
                }
            }
            //將最小值放在arr[i],即交換
            if (minIndex != i){//如果最小值的下標改變了則交換
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
    }

public static void insertSort(int[] arr){
        int insertIndex = 0;
        int insertValue = 0;
        for (int i = 1; i < arr.length; i++) {
            insertIndex = i - 1;
            insertValue = arr[i];
            while(insertIndex >= 0 && arr[insertIndex] > insertValue){
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            //優(yōu)化是否需要賦值
            if (insertIndex + 1 != i){
                arr[insertIndex + 1] = insertValue;
            }
        }
    }

public static void shellSort(int[] arr){
        int temp = 0;
        int count = 0;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]){//這里采用交換法
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }
    }

public static void shellSort(int[]arr){
        int count = 0;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int insertIndex = i - gap;
                int insertValue = arr[insertIndex + gap];
                while(insertIndex >= 0 && insertValue < arr[insertIndex]){
                    arr[insertIndex + gap] = arr[insertIndex];
                    insertIndex -= gap;
                }
                if (insertIndex != (i - gap)){
                    arr[insertIndex + gap] = insertValue;
                }
            }
        }
    }

 public static void quickSort(int[] arr,int left,int right){
        int r = right;
        int l = left;
        int temp = 0;
        int pivot = arr[(right + left) / 2];
        while(l < r){
            while(arr[l] < pivot){
                l++;
            }
            while(arr[r] > pivot){
                r--;
            }
            if(l == r)
                break;
            temp = arr[r];
            arr[r] = arr[l];
            arr[l] = temp;
            if (arr[l] == pivot){
                r--;
            }
            if (arr[r] == pivot){
                l++;
            }
        }
        if (l == r){
            l += 1;
            r -= 1;
        }
        //向左遞歸
        if(left < r){
            quickSort(arr,left,r);
        }
        //向右遞歸
        if(right > l){
            quickSort(arr,l,right);
        }
    }

/**
     *
     * @param arr   排序的原始數(shù)組
     * @param left  左邊有序序列的初始索引
     * @param mid   中間索引
     * @param right 右邊索引
     * @param temp  中轉數(shù)組
     */
    public static void merge(int[] arr,int left,int mid,int right,int[]temp){
        //System.out.println("*****");
        int i = left;
        int j = mid + 1;
        int t = 0;
        /*
        (一)
        先把兩邊有序的數(shù)據(jù)按照規(guī)則填充到temp數(shù)組
        指導左右兩邊的有序序列，有一邊處理完畢
        */
        while(i <= mid && j <= right){
            temp[t++] = arr[i] > arr[j] ? arr[j++] : arr[i++];
        }
        /*
        (二)
        把所有剩余數(shù)據(jù)的一邊一次全部填充到temp
         */
        while(i <= mid){
            temp[t++] = arr[i++];
        }
        while (j <= right){
            temp[t++] = arr[j++];
        }
        /*
        (三)
        將temp數(shù)組的元素拷貝到arr
         */
        t = 0;
        int tempLeft = left;
        //System.out.println("tempLeft = " + tempLeft + "right = " + right);
        while(tempLeft <= right){
            arr[tempLeft++] = temp[t++];
        }
    }

public static void mergeSort(int[] arr,int left,int right,int[] temp){
        if(left < right){
            int mid = (left + right) / 2;
            mergeSort(arr,left,mid,temp);
            mergeSort(arr,mid + 1,right,temp);
            merge(arr,left,mid,right,temp);
        }
    }

 public static void redixSort(int[]arr){
        //獲取數(shù)組中最大元素的位數(shù)
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if(max < arr[i])
                max = arr[i];
        }
        int maxLength = (max + "").length();
        //定義一個二維數(shù)組模擬桶
        int [][] bucket = new int[10][arr.length];
        //為了記錄每個桶中的元素個數(shù)定義一個一維數(shù)組
        int [] bucketElementCounts = new int[10];
        for (int i = 0, n = 1; i < maxLength; i++,n *= 10) {
            //入桶
            for (int j = 0; j < arr.length; j++) {
                int digitOfElement = arr[j] / n %10;
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            int index = 0;
            //出桶
            for (int j = 0; j < bucketElementCounts.length; j++) {
                if(bucketElementCounts[j] != 0){
                    for (int k = 0; k < bucketElementCounts[j]; k++) {
                        arr[index++] = bucket[j][k];
                    }
                }
                //取出元素后，需要將bucketElementCount中的元素清零
                bucketElementCounts[j] = 0;
            }
            //System.out.println("第" + (i + 1) + "次排序后的數(shù)組" + Arrays.toString(arr));
        }
    }

public static void main(String[] args) {
        System.out.println("測試排序算法的時間");
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)(Math.random() * 8000000);
        }
        Long startTime = System.currentTimeMillis();
        redixSort(arr);
        Long endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime + "ms");
    }