Bucket sorting字符串数组：索引、丢元素及空条目输出问题求助

Hey there! Let's work through those bucket sorting problems you're facing—they're totally normal when you're getting the hang of this algorithm, so let's break them down one by one.

1. Why Elements Are Going Missing #

The most common culprit here is incorrect bucket indexing when assigning elements to buckets. For example, if you're sorting by last name initials:

• If you don't handle uppercase/lowercase differences, a last name like "doe" might map to an invalid index (since 'd' - 'A' is a negative number) and get discarded.
• Or you might have a bucket array that's too small (like less than 26 buckets for A-Z), so some initials fall outside the array bounds.

Fix for Element Loss #

Make sure you normalize the initial to uppercase first, then calculate the index safely:

// Assuming buckets is a List<String> array of size 27 (26 for A-Z + 1 misc bucket)
for (String name : originalArray) {
    // Split to get last name (adjust this split logic to match your data format!)
    String lastName = name.split(" ")[1];
    char firstChar = Character.toUpperCase(lastName.charAt(0));
    // Check if the character is a letter to avoid out-of-bounds errors
    if (firstChar >= 'A' && firstChar <= 'Z') {
        int bucketIndex = firstChar - 'A';
        buckets[bucketIndex].add(name); // Add the full name to the correct bucket
    } else {
        // Handle non-letter initials (add to a "misc" bucket)
        buckets[26].add(name);
    }
}

Double-check that every element from your original array is being added to some bucket—no skipped entries!

2. Skipping Empty Buckets in Output #

Right now you're probably looping through all buckets, even the empty ones. To fix this, just add a check for empty buckets before processing or printing them:

Fix for Empty Bucket Output #

// When printing sorted buckets
for (List<String> bucket : buckets) {
    if (!bucket.isEmpty()) { // Only process non-empty buckets
        System.out.println("Sorted bucket: " + bucket);
    }
}

// When merging into the final sorted array
int currentIndex = 0;
String[] sortedArray = new String[originalArray.length];
for (List<String> bucket : buckets) {
    if (!bucket.isEmpty()) {
        bubbleSort(bucket); // Sort the bucket first with your bubble sort method
        // Copy each element from the bucket to the sorted array
        for (String name : bucket) {
            sortedArray[currentIndex++] = name;
        }
    }
}

This way, you won't see empty [] entries cluttering your console, and you'll only merge valid elements into your final array.

3. Fixing Merging Index Issues #

The index problem during merging usually happens because you're not tracking the current position in your sorted array correctly. The code above uses currentIndex to keep track of where the next element should go—each time you add an element from a bucket, you increment currentIndex so you don't overwrite existing elements.

Make sure your bubble sort method is correctly modifying the bucket list (it should sort the list in-place, not return a new list without updating the original bucket). For example, a simple in-place bubble sort for strings:

private static void bubbleSort(List<String> bucket) {
    int n = bucket.size();
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            // Compare last names (adjust this to match your sorting key!)
            String name1 = bucket.get(j);
            String name2 = bucket.get(j+1);
            String lastName1 = name1.split(" ")[1];
            String lastName2 = name2.split(" ")[1];
            if (lastName1.compareToIgnoreCase(lastName2) > 0) {
                // Swap elements
                String temp = bucket.get(j);
                bucket.set(j, bucket.get(j+1));
                bucket.set(j+1, temp);
            }
        }
    }
}

Quick Checklist to Verify #

• Every element from the original array is added to a bucket (no missing entries in your bucket assignment loop)
• You're checking for empty buckets before printing/merging
• Your merge loop uses a single currentIndex to track where to place elements in the sorted array
• Your bubble sort is sorting buckets in-place (not creating a new list that gets discarded)

Give these changes a try—they should resolve all three issues you're facing!

内容的提问来源于stack exchange，提问作者John Smith