在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基數排除字母排序的目的很小，除非它是一個您可以以這種方式訂購，或以這種方式專門給予您的任務，以使您的最終結果僅部分訂購。其次，在每次迭代之後排序的邏輯似乎並不存在。您必須在每次迭代時從每個桶中進行排序，以確保所有內容都按排序順序排列。