2

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

算法如下所示：

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));它说“线程中的异常”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));
  }
4

4 回答 4

3

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

但基本上，你坚持的一点是设置你的水桶。可能您希望您的存储桶成为Map<Character, List<String>>- 也就是说，您希望将每个字母 A - Z 映射到与该字母匹配的单词列表（对于您当前正在查看的位置）。那个单词列表就是你的桶。

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

于 2010-03-31T01:24:34.450 回答
1

在一个小清单上对此进行了测试；是的，为了家庭作业，我还必须这样做，为了您的方便，请留下评论，这样您就可以了解发生了什么，而不仅仅是复制粘贴（如果您这样做，您的 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);
            }
        }
    }
于 2016-04-26T23:37:43.363 回答
0

如果您不打算使用，则可以使用与@JacobMMap描述的相同的逻辑，但可以使用 List 数组。所以你创建.List<String>[] buckets = new List<String>[26]

于 2010-03-31T02:35:25.543 回答
0 
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]);
        }

    }




}
于 2014-04-22T17:50:06.970 回答