public class Test {

    public static void main(String[] args) {
        int[] arr = new int[]{17,35,37,32,63,46,24};
        System.out.println("原始數(shù)組："+ Arrays.toString(arr));
        bucketSort(arr);
        System.out.println("排序后的數(shù)組："+ Arrays.toString(arr));
    }



    //桶排序
    public static void bucketSort(int[] arr){

        int maxVal = Arrays.stream(arr).max().getAsInt();
        int minVal = Arrays.stream(arr).min().getAsInt();

        //計算桶的數(shù)量，+1 是保證至少有1個桶來裝數(shù)據(jù)
        int bucketCount  = (maxVal - minVal)/arr.length + 1;

        // 用于存儲每個桶中元素的出現(xiàn)次數(shù)
        int[] order = new int[bucketCount];
        // 用于存儲每個桶中的數(shù)據(jù)
        int[][] output = new int[bucketCount][arr.length];

        int len = arr.length;

        //每個桶中數(shù)據(jù)的范圍,+1 是至少每個桶中的數(shù)據(jù)范圍為1
        int rang =  (maxVal - minVal)/bucketCount +1;

        //將待排序的數(shù)組中的所有元素放入到桶中
        for(int i = 0; i < len; i++ ){
            //計算數(shù)組元素所在的桶
            int index = (arr[i] - minVal)  /  rang ;
            //將元素放入指定的桶
            output[index][order[index]] = arr[i];
            //添加桶元素的計數(shù)
            order[index]++;
        }

        System.out.println("桶計數(shù)數(shù)組為："+ Arrays.toString(order));

        int k = 0;

        //遍歷桶，將桶中的元素放入源數(shù)組中，并對其進行快速排序
        for(int i = 0; i < bucketCount; i++){
            int j ;
            if(order[i] > 0){
                // 將桶中的元素放入源數(shù)組中
                for(j = 0; j < order[i]; j++){
                    arr[k++] = output[i][j];
                }
                //對桶中的元素進行快速排序
                quickSort(arr,k-j,k-1);
            }

        }
    }


    //快速排序的詳解請參考歷史博文 `深入了解快速排序：原理、性能分析與 Java 實現(xiàn)`
    public static void quickSort(int[] arr,int left,int right) {

        //遞歸結束條件left < right
        if(left < right){
            // 通過分區(qū)函數(shù)得到基準元素的索引
            int pivotIndex = partition(arr, left, right);
            //遞歸對基準元素左邊的子數(shù)組進行快速排序
            quickSort(arr,left,pivotIndex-1);
            //遞歸對基準元素右邊的子數(shù)組進行快速排序
            quickSort(arr,pivotIndex+1,right);
        }
    }

    public static int partition(int[] arr,int left,int right) {
        // 選擇最后一個元素作為基準元素
        int pivot = arr[right];
        int i = left;

        //循環(huán)數(shù)組，如果滿足條件，則將滿足條件的元素交換到arr[i]，同時i++,循環(huán)完成之后i之前的元素則全部為小于基準元素的元素
        for (int j = left; j < right; j++) {
            if(arr[j] < pivot){
                if(j != i){
                    int temp  = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
                i++;
            }
        }

        // 交換 arr[i] 和基準元素
        int temp = arr[i];
        arr[i] = arr[right];
        arr[right] = temp;

        //返回基準元素的下標
        return i;
    }
}

原始數(shù)組：[17, 35, 37, 32, 63, 46, 24]
桶計數(shù)數(shù)組為：[1, 1, 3, 0, 1, 0, 1]
排序后的數(shù)組：[17, 24, 32, 35, 37, 46, 63]