java - 桶排序中的桶大小

Question

我正在尝试为桶排序编写代码，但对每个桶的桶大小感到困惑。我的代码如下。 输入数组:{12, 11, 13, 5, 6, 7,10,22,4,16,1,26};

我正在传递每个桶的桶大小 >3 然后我没有按排序顺序获得输出。它为桶大小 1 和 2 提供了完美的答案

public void bucsort(int[] arr,int bucketSize){

        if(arr.length==0) return;

        int max=arr[0];
        int min=arr[0];

        for(int i=0; i<arr.length;i++){
            if(arr[i]<min)
            {
                min=arr[i];
            }
            else
                max=arr[i];
        }
        int bucketCount= (max - min) / bucketSize + 1;
         List<List<Integer>> buckets = new ArrayList<List<Integer>>(bucketCount);
        // int divider= (max+1)/bucketCount;

         for (int i = 0; i < bucketCount; i++) {
                buckets.add(new ArrayList<Integer>());
            }
         for (int i = 0; i < arr.length; i++) {

                buckets.get((arr[i]-min) / bucketSize).add(arr[i]);
            }
         int currentIndex = 0;
            for (int i = 0; i < buckets.size(); i++) {
                Integer[] bucketArray = new Integer[buckets.get(i).size()];
                bucketArray = buckets.get(i).toArray(bucketArray);
                InsertionSort(bucketArray);
                for (int j = 0; j < bucketArray.length; j++) {
                    arr[currentIndex++] = bucketArray[j];
                }
            }       
    }

没有什么关系。桶的数量及其大小？

我为 max-min 函数编辑了我的方法，还调试了程序。我的插入排序似乎有一些错误

代码是:

public void InsertionSort(Integer[] arr){


        for(int i=1; i<arr.length; i++){
            int value=arr[i];
            int hole=i;

            while(hole>0 && arr[hole-1]>value){

                arr[hole]=arr[hole-1];

                hole--;
            }

            arr[hole-1]=value;
        }
    }

主要功能

public static void main(String[] args) {

        int arr[] = {12, 11, 13, 5, 6, 7,10,22,4,16,1,26};

        BucketSort ob = new BucketSort();
        ob.bucsort(arr, 5);
        printArray(arr);
    }
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

桶大小 5 的输出:5 1 4 6 7 10 12 11 13 16 22 26 对于尺寸 3:1 5 4 6 7 12 10 11 13 16 22 26 对于尺寸 2:1 4 5 6 7 10 12 11 13 16 22 26

Answer 1

寻找最大最小值是错误的...(你有一些逻辑错误)

int minValue = array[0];
        int maxValue = array[0];
        for (int i = 1; i < array.Length; i++) {
            if (array[i] < minValue) {
                minValue = array[i];
            } else if (array[i] > maxValue) {
                maxValue = array[i];
            }
        }

在您的代码上:

     1 4 3 
min  1 1 1
max  1 4 3

这才是正确的实现方式

for (i = 1; i < length; i++) {
            j = i;
            while (j > 0 && arr[j - 1] > arr[j]) {
                  tmp = arr[j];
                  arr[j] = arr[j - 1];
                  arr[j - 1] = tmp;
                  j--;
            }
}

有时间我会调试你的代码..