//參數(shù)傳入數(shù)組arr ， 最左邊的下標(biāo)left，最右邊的下標(biāo) right
public static void quickSort(int[] arr , int left , int right){
        //分別用臨時(shí)變量代替
        int l = left;
        int r = right;
        //中間的下標(biāo)
        int middle = arr[(left + right) / 2];
        //臨時(shí)變量，用于交換數(shù)據(jù)
        int temp = 0;
        //進(jìn)行循環(huán)，只要右邊的下標(biāo) l 小于 左邊的下標(biāo) r 就進(jìn)行循環(huán)
        while (l < r){
            //左邊l 到 中間middle 單獨(dú)循環(huán)，找到比middle大的值
            while (arr[l] < middle){
                l += 1;
            }
            //中間middle 到 右邊 r 單獨(dú)循環(huán)，找到比middle小的值
            while (arr[r] > middle){
                r -= 1;
            }
            //退出循環(huán)，表示找到，不過(guò)先判斷 l 是否大于等于 r 
            //滿足就可以退出循環(huán)，不需要執(zhí)行下面的代碼了
            if(l >= r){
                break;
            }
            //找到的數(shù)據(jù)進(jìn)行交換
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            //此時(shí)進(jìn)行判斷，如果arr[l] 等于middle  則 r--
            if(arr[l] == middle){
                r -= 1;
            }
            //如果  arr[r] 等于middle 則 l++
            if(arr[r] == middle){
                l += 1;
            }
        }
        //退出循環(huán)，l 會(huì)等于 r，此時(shí)要將兩者移位，l進(jìn)行加一，r進(jìn)行減一
        if(l == r){
            l += 1;
            r -= 1;
        }
        //第一輪完成后進(jìn)行遞歸
        //重復(fù)上面的方法，向左遞歸
        if(left < r){
            //r 繼續(xù)往前移的，所以左下標(biāo)為left ，右下標(biāo)為 r
            quickSort(arr, left , r);
        }
        //重復(fù)上面的操作，向右遞歸
        if(right > l){
            //l 繼續(xù)往后移的，所以左下標(biāo)為 l ，右下標(biāo)為 right
            quickSort(arr, l , right);
        }
    }

public static void merger(int[] arr , int left ,int mid , int right , int[] temp){
        int i = left;
        int j = mid + 1;
        int t = 0;//數(shù)組temp的下標(biāo)
        //將arr數(shù)組按順序放入temp 數(shù)組
        while (i <= mid  && j <= right){
            //從中間分隔開(kāi)，左邊和右邊相互比較
            //如果左邊更小，先放入temp數(shù)組，否則右邊先放入
            if(arr[i] < arr[j]){
                temp[t] = arr[i];
                i++;
                t++;
            }else {
                temp[t] = arr[j];
                j++;
                t++;
            }
        }
        //有可能有一邊還沒(méi)放完，于是繼續(xù)循環(huán)放放入
        //左邊沒(méi)放完
        while (i <= mid){
            temp[t] = arr[i];
            t++;
            i++;
        }
        //右邊沒(méi)放完
        while (j <= right){
            temp[t] = arr[j];
            j++;
            t++;
        }
        //將temp中數(shù)據(jù)拷入到arr
        t = 0;
        int leftind = left;
        //第一次（leftind，right）是（0,1）（2,3）（4,5）（6,7）
        //第二次（leftind，right）是（0,3）（4,7）
        //第三次（leftind，right）是（0,7）
        while (leftind <= right){
            arr[leftind] = temp[t];
            t++;
            leftind++;
        }
    }

public static void mergerSort(int[] arr, int left,int right, int[] temp){
        //判斷
        if (left < right){
            //求出中間值
            int mid = (left + right) / 2;
            //調(diào)用自己，向左遞歸
            mergerSort(arr, left, mid , temp);
            //調(diào)用自己，向右遞歸
            mergerSort(arr , mid + 1, right, temp);
            //調(diào)用merger進(jìn)行合并
            merger(arr, left , mid, right, temp);
        }
    }

public static void cardinalitySort(int[] arr){
        //首先找到數(shù)組中最大數(shù)的位數(shù)
        int max = arr[0];
        for(int i = 1; i < arr.length - 1; i++ ){
            if(arr[i] > max){
                max = arr[i];
            }
        }
        int maxLength = (max + "").length();
        //定義10個(gè)桶，每個(gè)桶大小為數(shù)組大小
        int[][] bucket = new int[10][arr.length];
        //定義一個(gè)數(shù)組來(lái)表示每個(gè)桶存放的數(shù)據(jù)
        int[] bucketcount = new int[10];
        //n是用來(lái)進(jìn)行位數(shù)處理的
        for(int i = 1, n = 1; i <= maxLength ; i++,n *= 10){
            for(int j = 0; j < arr.length ; j++){
                //對(duì)每位數(shù)進(jìn)行位處理，并放入桶中
                int elentData = arr[j] / n % 10;
                /*    
                  放對(duì)應(yīng)的桶中,
                  bucketcount[elentData]表示對(duì)應(yīng)的桶的數(shù)據(jù),
                  假如第一個(gè)數(shù)為579，要放入bucketcount[9]（第九個(gè)桶）的第一個(gè)位置，
                  默認(rèn)初始化為0，所以第一個(gè)數(shù)放入的位置是bucketcount[9] = 0
                */
                bucket[elentData][bucketcount[elentData]] = arr[j];
                //第一個(gè)數(shù)放完后，這個(gè)桶中數(shù)據(jù)進(jìn)行++，
                //下次再放入這個(gè)桶時(shí)，bucketcount[9] = 1
                bucketcount[elentData]++;
            }
            int index = 0;
            //遍歷每一個(gè)桶
            for(int k = 0; k < bucketcount.length; k++){
                //第一次默認(rèn)為bucketcount[k] = 0
                //所以如果第一個(gè)數(shù)為零，就說(shuō)明這個(gè)桶為空
                if(bucketcount[k] != 0){
                    //有數(shù)據(jù)，則桶bucketcount[k]就會(huì)有對(duì)應(yīng)數(shù)據(jù)多少的大小，進(jìn)行遍歷
                    for(int l = 0; l < bucketcount[k] ; l++){
                        //放入原來(lái)的數(shù)組
                        arr[index++] = bucket[k][l];
                    }
                }
                //桶中的數(shù)放回原數(shù)組放完后，進(jìn)行置空
                bucketcount[k] = 0;
            }
        }
    }