Java 对字符串进行桶排序

Question

我不知道使用桶排序对始终具有相同长度的字符串列表进行排序的最佳方法是什么。

算法如下所示：

For the last character position down to the first:
    For each word in the list:
        Place the word into the appropriate bucket by current character
    For each of the 26 buckets(arraylists)
        Copy every word back to the list

我正在用 java 编写，并且使用 arraylist 作为存储未排序字符串的主列表。每个字符串的长度为五个字符。

这就是我开始的。它只是在第二个 for 循环中突然停止，因为我不知道下一步该做什么，也不知道我是否正确地完成了第一部分。

ArrayList<String> count = new ArrayList<String>(26);

for (int i = wordlen; i > 0; i--) {
    for (int j = 0; i < myList.size(); i++)
        myList.get(j).charAt(i)
}

提前致谢。

编辑：这就是我现在所拥有的。我知道这是行不通的，因为如果有多个字符串以相同的字母开头，那么它就会爆炸，但我认为我的方向更正确。当我运行它时，即使我输入了单词以确保没有重复的字母，它也会在第一组行上崩溃： count.set(myList.get(j).charAt(i), myList.get(j)); 它说“线程“main”中出现异常 java.lang.StringIndexOutOfBoundsException：字符串索引超出范围：5”

 public void BucketSort(int wordlen) {

   ArrayList<String> count = new ArrayList<String>(26);

     //Make it so count has a size
   for(int p = 0; p < 26; p++)
       count.add(null);

    for (int i = wordlen; i > 0; i--) { //for each letter
        for (int j = 0; j < myList.size(); j++) //for each word
               //Add the word to count based on the letter
            count.add((int)myList.get(j).charAt(i) - 65, myList.get(j));
}
     //Clear the main list so there aren't a bunch of unsorted words leftover
   myList.clear();

     //Add the words back in to the list based on their order in count
   for (int m = 0; m < 26; m++)
       myList.add(count.get(m));
  }

Answer 1

这对我来说就像是家庭作业，所以我不会用代码解决方案来回应。

但基本上，你所要做的就是设置你的水桶。也许您希望您的存储桶是一个 Map> ——也就是说，您希望将每个字母 A - Z 映射到与该字母匹配的单词列表（例如您当前正在查看的位置）。该单词列表就是您的存储桶。

然后，完成内部循环后，从 AZ 开始对地图的内容进行另一个循环（提示：for ( char ch = 'A'; ch <= 'Z' ; ch++ )) 并将相应存储桶的内容转储回您的（清空的）列表中。

Answer 2

在一个小列表上测试了这个；是的，我也必须这样做作为家庭作业，并且为了您的方便留下评论，这样您就可以了解发生了什么，而不仅仅是复制粘贴它（如果您这样做，您的 OV 分数将是 100%！）。

public static void sort(String[] array) {
        if (array.length == 0) return;  // empty check

        // Determine max length
        int max = 0;
        for (int i = 1; i < array.length; i++) {
            // update max length
            if (max < array[i].length()) max = array[i].length();
        }


        // Initialize buckets
        int bucketCount = 26;   // alphabet
        // buckets in maps
        HashMap<Character, Vector<String>> buckets = new HashMap<Character, Vector<String>>(bucketCount);
        // create the buckets
        char a = 'a';
        for (int i = 0; i <= bucketCount; i++, a++){
            buckets.put(a, new Vector<String>());
        }   

        // assign array values into buckets
        for (int i = 0; i < array.length; i++) {
            // get first letter of word
            String current = array[i];
            char letter = current.toLowerCase().charAt(0);
            buckets.get(letter).add(array[i]);
        }

        // Sort buckets and place back into input array
        int index = 0;  // keeps global array index
        for (char key = 'a'; key <= 'z'; key++) {
            // retrieve the bucker
            Vector<String> bucket = buckets.get(key);

            // do an insertion sort on bucket
            for (int i = 1; i < bucket.size(); i++){
                // i starts as 1, as a list of size 1 is already sorted

                // save the value at the index and remove it
                String temp = bucket.get(i);
                bucket.remove(i);

                // move all values one up, until we find the saved value's location
                int j;
                for(j = i-1; j >= 0 && 
                        bucket.get(j).compareToIgnoreCase(temp) > 0; j--){
                    // to "insert", we need to add and remove
                    bucket.add(j+1, bucket.get(j));
                    bucket.remove(j);
                }
                // place the saved value in the proper location
                bucket.add(j+1, temp);
            }


            // pile the current bucket back into array
            for (int j = 0; j < bucket.size(); j++) {
                array[index++] = bucket.get(j);
            }
        }
    }

Answer 3

如果您不打算使用 Map，则可以使用 @JacobM 但有一个 List 数组。因此，您创建 List[] buckets = new List[26]。

Answer 4

public void bucketSort(String[] words)
{

    int maxlength=0;
    for(int i=0;i<words.length;i++)
    {
        words[i] = words[i].toUpperCase();
        if(maxlength<words[i].length())
            maxlength = words[i].length();

    }

    for(int j=maxlength-1;j>=0;j--)
    {

        Vector<Vector<String>> map = new Vector<Vector<String>>();
        for(int i=0;i<27;i++)
        {
            map.add(null);
        }
        for(int i=0;i<words.length;i++)//Add words of of length j or greater to map(which is bucket here)
        {

            if(words[i].length()>j)
            {
                int val = (int)words[i].charAt(j) -65;
                if(map.get(val)!= null)
                {
                    map.get(val).add(words[i]);
                }
                else
                {
                    Vector<String> vecot = new Vector<String>();
                    vecot.add(words[i]);
                    map.add(val, vecot);
                }
            }
            else///Add words of of length<j to bucket 0
            {
                if(map.get(0) != null)
                {
                    map.get(0).add(words[i]);
                }
                else
                {
                    Vector<String> vecot = new Vector<String>();
                    vecot.add(words[i]);
                    map.add(0, vecot);
                }

            }
        }
        int count =0;
        for(int i=0;i<map.size();i++)
        {

            if(map.get(i)!=null)
            {
                for(int k=0;k<map.get(i).size();k++)
                {
                 words[count]=map.get(i).get(k); 
                 count++;
                }
            }
        }
        System.out.println("Next set :");
        for(int i=0;i<words.length;i++)
        {
            System.out.println(words[i]);
        }

    }




}