抱歉我的英语不好。我正在设计 LSD 字符串排序算法,我有一个与之相关的问题。这是我的代码。我希望输入 W not fixed,例如:
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);
}
}
最佳答案
要开发适用于可变长度字符串的 LSD 字符串排序的实现,我们需要在您的代码的基础上做很多工作。我们需要找到 string[] 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]);
}
}
}
关于java - 如何在不输入固定长度的情况下使用LSD String Sort?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37619532/