在Java中使用相反顺序的基数排序

Question

Im无法理解基数排序。我应该整理这个词的最后一个字母，就像从右向左整理，直到没有更多的字母被留下。

文本文件看起来像这样

酒吧 猫 苹果 错误 COG 跳跃 鹿茸 脚踝 熊

我的输出这样

脚踝 鹿茸 苹果 酒吧 熊 错误 跳跃 猫 COG

但我应该得到这样

酒吧 错误 猫 COG 熊 脚踝 苹果 雀跃输出 鹿角

感觉就像我接近有正确的代码，但我卡住了，不知道还有什么要做。这将不胜感激，如果我能得到帮助，并指出我在正确的方向

这是我做的代码

RadixSort.java

public class RadixSort { 
     public static void main(String[]args) throws FileNotFoundException{ 
    Linkedlist[] allNameLinkedList = new Linkedlist[26]; // create an array 
     of LinkedList for 26 letters in alphabets 
    int count = 0; 
    // initialize all the elements in the array to new LinkedList 
    for (int i = 0; i < allNameLinkedList.length; i++) { 
     allNameLinkedList[i] = new Linkedlist(); 
    } 
    Scanner scan = new Scanner(new File("words.txt")); 

    while(scan.hasNextLine()) 
    { 
     String currentname = scan.nextLine(); 
     for(int i = 0; i < 26; i++){ 
      if(currentname.charAt(2) == (char)(i+97)) 
      { 
       allNameLinkedList[i].addNodeToTheEndOfTheList(currentname); 
      } 
     } 
     count++; 
    } 

    // copy sorted nodes to new LinkedList called container 
    Linkedlist container = new Linkedlist(); 
    for (int i = 0; i < 26; i++) { 
     Node n = allNameLinkedList[i].front; 

     while(n != null){ 
      container.addNodeToTheEndOfTheList(n.name); 
      n = n.next; 
     } 
    } 
    // empty all the elements of array 
    for (int i = 0; i < allNameLinkedList.length; i++) { 
     allNameLinkedList[i] = new Linkedlist(); 
    } 

    Node m = container.front; 
    while(m!=null) 
    { 
     String currentname = m.name; 
     for(int i = 0; i < 26; i++){ 
      if(currentname.charAt(1) == (char)(i+97)) 
      { 
       allNameLinkedList[i].addNodeToTheEndOfTheList(currentname); 
      } 
     } 
     m = m.next; 
     count++; 
    } 
    container = new Linkedlist(); 
    for (int i = 0; i < 26; i++) { 
     m = allNameLinkedList[i].front; 

     while(m!=null){ 
      container.addNodeToTheEndOfTheList(m.name); 
      m = m.next; 
     } 
    } 
    for (int i = 0; i < allNameLinkedList.length; i++) { 
     allNameLinkedList[i] = new Linkedlist(); 
    } 
    m = container.front; 

    while(m!=null) 
    { 
     String currentname = m.name; 

     for(int i = 0; i < 26; i++){ 
      if(currentname.charAt(0) == (char)(i+97)) 
      { 
       allNameLinkedList[i].addNodeToTheEndOfTheList(currentname); 
      } 
     } 
     m = m.next; 
     count++; 
    } 
    container = new Linkedlist(); 
    for (int i = 0; i < 26; i++) { 
     m = allNameLinkedList[i].front; 

     while(m!=null){ 
      System.out.println(m.name); 
      container.addNodeToTheEndOfTheList(m.name); 
      m = m.next; 
     } 
    } 
    scan.close(); 
    System.out.println("The total number of comparisions was :"+count); 
    } 
    } 

Answer 1

您的问题是只排序第一个字符。

while(m!=null) 
    { 
     String currentname = m.name; 

     for(int i = 0; i < 26; i++){ 
      // charAt(0) is first character in String 
      if(currentname.charAt(0) == (char)(i+97)) 
      { 
       allNameLinkedList[i].addNodeToTheEndOfTheList(currentname); 
      } 
     } 
     m = m.next; 
     count++; 
    } 

你必须遍历每个字符，而不仅仅是第一个字符。这解释了为什么你的排序是按字母顺序。它是如何在完美的字典顺序是超越我。该代码片段将仅基于charAt（0）将数据分类到其链接列表“桶”中。

您的输入和输出看起来好像没有加起来一样，因为输入是未排序的，而您的输出实际上是您应该具备的字母排序类型：MSD基数排序。

最重要的数字是你想要进行字母比较的原因，因为在字典顺序的情况下，较高的比较幅度是第一个字符。其他排序可能是整数比较中的LSD（最低有效数字），但应该警告您，由于您必须担心不同的长度字符串，因此应该警告LSD基数排序在这里不足。

随着MSD基数排序，没什么大不了的。你只要确保你没有超过一个单词的范围，并且在它被放置之后不要移动它，除非它被另一个单词移动。使用LSD，你必须向后索引，首先检查你的current word length - current index > 0，然后再继续按照你的实际charAt进行排序，然后你的最终结果可能永远不会按照字母顺序排列 - 我认为LSD基数排除字母排序的目的很小，除非它是一个您可以以这种方式订购，或以这种方式专门给予您的任务，以使您的最终结果仅部分订购。其次，在每次迭代之后排序的逻辑似乎并不存在。您必须在每次迭代时从每个桶中进行排序，以确保所有内容都按排序顺序排列。