Как использовать LSD String Сортировать без ввода фиксированной длины?

Question

извините за мой плохой английский. Я styding LSD String Сортирует алгоритм, и у меня есть вопрос, связанный с ним. Вот мой код. Я хочу, чтобы вход W не фиксировался, например:

String[] a = {"38A", "3TW723", "2IYEA938", "3CI34780720"}; 

public static void sort(String[] a, int w) { // Sort a[] on leading W characters. 
     int R = 256; 
     int N = a.length; 
     //For each of the character from right to left 
     for (int d = w - 1; d >= 0; d--) { 
      //1. count the frequencies 
      int[] count = new int[R + 1]; 
      for (int i = 0; i < N; i++) { 
       count[a[i].charAt(d) + 1]++; 
      } 
      //2. Transform counts to indices 
      for (int r = 0; r < R; r++) { 
       count[r + 1] += count[r]; 
      } 
      //3. Distribute 
      String aux[] = new String[N]; 
      for (int i = 0; i < N; i++) { 
       aux[count[a[i].charAt(d)]] = a[i]; 
       count[a[i].charAt(d)]++; 
      } 
      //4. Copyback 
      System.arraycopy(aux, 0, a, 0, N); 
     } 
    } 

Answer 1

LSD сортирует только строки фиксированной длины. Вместо этого используйте MSD

Answer 2

Чтобы разработать реализацию строковой сортировки LSD, которая работает для строк переменной длины, нам нужно сделать много работ на основе вашего кода. Нам нужно найти самую длинную длину строки в строке [] a, поэтому, когда d> = a [i] .length(), мы возвращаем 0, что означает добавление дополнительного 0, чтобы каждая строка была одинаковой длины. Это мой код.

// Develop an implementation of LSD string sort 
// that works for variable-length strings. 
public class LSDForVariableLengthStrings { 

    // do not instantiate 
    private LSDForVariableLengthStrings() { } 

    // find longest length string in string[] a. 
    public static int findLongestLength(String[] a) { 
     int longest = 0; 
     for (int i = 0; i < a.length; ++i) { 
      if (a[i].length() > longest) { 
       longest = a[i].length(); 
      } 
     } 
     return longest; 
    } 

    // if d >= 0 && d < a[i].length(), return a[i].charAt(d); 
    // else , return 0, which means least value to sort. 
    public static int findCharAtInString(int i, int d, String[] a) { 
     if (d < 0 || d >= a[i].length()) { 
      return 0; 
     } 
     return a[i].charAt(d); 
    } 

    // Rearranges the array of variable-length strings. 
    public static void sort(String[] a) { 
     int n = a.length; 
     int R = 256; // extended ASCII alphabet size. 
     String[] aux = new String[n]; 
     int w = findLongestLength(a); // w is the length of longest string in a. 
     for (int d = w - 1; d >= 0; d--) { 
      // sort by key-indexed counting on dth character 

      // compute frequency counts 
      int[] count = new int[R + 1]; 
      for (int i = 0; i < n; ++i) { 
       int c = findCharAtInString(i, d, a); 
       count[c + 1]++; 
      } 

      // compute cumulates 
      for (int r = 0; r < R; ++r) { 
       count[r + 1] += count[r]; 
      } 

      // move data 
      for (int i = 0; i < n; ++i) { 
       int c = findCharAtInString(i, d, a); 
       aux[count[c]++] = a[i]; 
      } 

      // copy back 
      for (int i = 0; i < n; ++i) { 
       a[i] = aux[i]; 
      } 
     } 
    } 
    public static void main(String[] args) { 

     String[] a = {"38A", "3TW723", "2IYEA938", "3CI34780720"}; 
     int n = a.length; 
     // sort the strings 
     sort(a); 

     // prints results 
     for (int i = 0; i < n; ++i) { 
      System.out.println(a[i]); 
     } 

    } 
}