解释这个简单的程序——桶排序

Question

int[] a 在这段代码中做了什么？

public class BucketSort_main {

    public static void main(String[] args) {  
        int[] numbers = new int [5]; //create an array to house the numbers generated
        int[] sortedArray = new int [5]; //create array to be a temp housing for the numbers 
        int [][] bucket = new int [10][numbers.length]; //creates 2D array of 0-9
        int [] a = new int [10]; 
        int divisor = 1; 
        int digitCount = 1; 
        boolean moreDigits = true; 


        //fill the array and array to be sorted with the random numbers 0 - 100
        for (int i = 0; i < numbers.length; i++) { 
            numbers [i] = (int)(Math.random()*100); 
            sortedArray [i] = numbers [i]; 
        } 


        System.out.println("UnSorted Numbers");

        for (int i = 0; i< numbers.length; i++){ 
            System.out.println (numbers[i]); 
        }
    }

    System.out.println("\n");

    int[] tempArray = new int[10]; //creatE a temp array of size equal to the amount of buckets

    while (moreDigits) { 
        moreDigits = false; 

        for (int i = 0; i < tempArray.length; i++){ 
            tempArray[i]= -1;  //initailze to make sure a null pointer is not hit
        }

        for (int i = 0; i < numbers.length; i++){ 
            int tmp = sortedArray[i] / divisor; //create a temp int of the array value / divisor to get its single digit value

            if (tmp/10 != 0){
                moreDigits = true; 
            }

            int numPlace = tmp % 10; 

            tempArray[numPlace] = sortedArray[i];  //at the digits "ones"/tens value for row index, set the number from the sorted array into that index
            bucket [numPlace][a[numPlace]] = sortedArray[i]; //place the numbers into the proper coord of the bucket.

            //Print statements used for DEBUGGING
            System.out.println("Number: " + tempArray[numPlace] +" Has Digit "+digitCount+" equal to "+ numPlace); 

           // bucket [digit][a[digit]] = tempArray[i]; 

            //row may seem "off" to user, but the row prints based on 0 - n
            System.out.println ("Digit " + numPlace + " moved into row " + a[numPlace] + ". " + bucket[numPlace][a[numPlace]]); 
            System.out.println (" "); 

            a[numPlace]++; 

        }     
        digitCount++; 
        divisor *= 10; //multipy the divisor by 10 to move to the next 1s. 10s, or 100s place

        int j = 0; //iteration for tempNumbersArray

        for (int x = 0; x < 10; x++) { 
            a[x] = 0; 
            for (int y = 0; y < numbers.length; y++){ 
                if (bucket[x][y] != 0) {//see if value in bucket is a zero, if it is dont print it
                    sortedArray [j] = bucket[x][y]; //set sorted array value equal to the value at row/col index of bucket
                    bucket[x][y] = 0; //set that spot that was just copied over to zero
                    j++; //increment to the next index of sorted array
                }                     
            }  
        }  
    }   //end while  

    System.out.println("Sorted Numbers:");

    for (int i = 0; i < numbers.length; i++) { 
        System.out.println (sortedArray[i]); 
     }
}

Answer 1

'a' 数组保存了某个桶保存的条目数。每次向 bucket x 中添加东西时，a[x] 的值都会增加 1。

所以'a'只是用来记账的。这可以通过改变

来避免

 bucket [numPlace][a[numPlace]] = sortedArray[i];

在

 bucket [numPlace][bucket[numPlace].length] = sortedArray[i];

和

 System.out.println ("Digit " + numPlace + " moved into row " + a[numPlace] + ". " + bucket[numPlace][a[numPlace]]);

在

 System.out.println ("Digit " + numPlace + " moved into row " + bucket[numPlace].length + ". " + bucket[numPlace][a[numPlace]]);

并删除

a[numPlace]++;

解释这个简单的程序——桶排序

explaining this simple program - bucket sort

java

bucket-sort