logo标签列表

按逻辑对大小写字母和数字混合字符串进行排序

javaalgorithmsorting
5
我有一个由大写字母和数字组成的字符串，需要“逻辑”排序并存储在数据库字段中。我已经解决了更新/更改/查询数据库部分的问题，但是在逻辑上排序这个字符串方面遇到了困难。
给定以下一组字符串： AB1 AB2 AB3 A11 AB10
我需要按字母顺序进行排序，如下所示： A11 AB1 AB2 AB3 AB10
为了实现这一点，我认为需要对字符串进行拆分。因为当前尝试按字母顺序排序会得到 A11 AB1 AB10 AB2 AB3
编辑：我需要能够存储一个已拆分的字符串和一个未拆分的字符串，以便与其他程序进行排序。
以下是我认为它们需要被拆分并排序的方式。
A11  -  A   11
AB1  -  AB   1
AB2  -  AB   2
AB3  -  AB   3
AB10 -  AB  10

以下是一些常量，字符串长度不会超过5个字符，只包含大写字母和数字。

这是我的代码进展到的地方。我遇到了写作障碍，希望能得到一些帮助。我认为我需要找出它是否以字母开头，然后找出所有连续的字母，左对齐它们，接着处理数字，找出所有连续的数字并右对齐它们。不确定像'A1B1'这样的情况该如何处理...

for(int ii = 0;ii < sectionString.length() && ii< SECTIONSPACES;ii++){
               System.out.print("    Was previous a number? " + isPreviousANumber +         "\n");
try{
    String tmpString = sectionString.substring(ii,ii + 1 );
    int positionInCharArray = Integer.parseInt(tmpString);
    System.out.printf("    Position " + ii + " is number " + positionInCharArray + "\n");
    isPreviousANumber = true;        
}catch(Exception e){
    System.out.printf("    Position " + ii + " number is not a number " +      sectionString.substring(ii,ii) + "\n");
    isPreviousANumber = false;
    }                   
}
使用类似于基数排序的算法，数字优先于字母。 - arynaq
我会复制下面我发表的评论：如果我可以使用Java对它们进行排序，那么这些工作非常出色。问题在于不同的程序需要对它们进行排序，并且为了与它们兼容，我需要“爆炸”字符串并使用爆炸后的字符串进行排序，只显示常规值。我知道这不是“正常”的做法。在数据库中将有两个字段，一个称为section，另一个字段称为sort_section。有意义吗？ - nkuebelbeck
6个回答
1
这里是我使用基数排序思想对其进行排序的方式：

public static String[] radixSort(String[] strings){
    // Pad the strings
    for(int i=0; i<strings.length; i++){
        strings[i] = String.format("%-5s", strings[i]);
    }

    // Radix sort them
    for (int digit = 0; digit < 5; digit++) {
        final int i = digit;
        Arrays.sort(strings, new Comparator<String>() {


            @Override
            public int compare(String o1, String o2) {
                return o1.charAt(i) - o2.charAt(i);
            }
        });
    }

    // Then trim the whitespaces we used to pad

    for (int i = 0; i < strings.length; i++) {
        strings[i] = strings[i].trim();
    }

    return strings;
}

带有输入的代码。
    String[] strings = new String[] { "AB1", "AB2", "AB3", "A11", "AB10" };
    System.out.println(Arrays.toString(radixSort(strings)));

和输出

[A11, AB1, AB2, AB3, AB10]

我不确定这是最有效的方法，但它可以完成任务。

如果我可以使用Java对它们进行排序，那么这些工作非常出色。问题在于不同的程序需要对它们进行排序，并且为了与它们兼容，我需要“爆炸”它们并使用爆炸后的字符串进行排序，只显示常规值。我知道这不是“正常”的做法。在数据库中将有两个字段，一个称为section，另一个称为sort_section。明白吗？ - nkuebelbeck
不知道第二个要求，像马可建议的那样将它们包装在另一个对象中是正确的方法，可以添加getter或使用正则表达式将我排序的字符串拆分为字母和数字值。 - arynaq
那是我的错，我把那个要求添加到了原始帖子中。 - nkuebelbeck
没问题 :) 我也经常忘记在发布问题时注意这个。有时候，我甚至在设计完之后才想起某个限制，这就迫使我不得不进行完全重写。 - arynaq
1
你可以使用另一个类作为字符串的特殊表示。例如：

你可以这样做：

public class AlphaNumericString implements Comparable<AlphaNumericString> {
    public final String alphaPart;
    public final Long numericPart;

    public AlphaNumericString(String string) {
        int index = 0;
        while (index < string.length() && !Character.isDigit(string.charAt(index))) {
            index++;
        }

        alphaPart = string.substring(0, index);

        if (index < string.length()) {
            numericPart = new Long(string.substring(index));
        } else {
            numericPart = null;
        }
    }

    @Override
    public int compareTo(AlphaNumericString other) {
        int stringCompareResult = alphaPart != null ? alphaPart.compareTo(other.alphaPart) : -1;

        if (stringCompareResult == 0) {
            return numericPart != null ? numericPart.compareTo(other.numericPart) : -1;
        } else {
            return stringCompareResult;
        }
    }

    @Override
    public String toString() {
        return (alphaPart != null ? alphaPart : "") + (numericPart != null ? numericPart : "");
    }
}

你可以将当前的字符串转换为这个类，根据需要进行排序并再次转换。
1
这句话“不确定像‘A1B1’这样的东西会如何工作…”增加了问题的复杂性。以下方法适用于所有情况。
方法：
将字符串分成标记。标记可以是字母或连续的数字序列。使用前导空格填充每个数字标记以使其达到五个字符。将标记连接起来以制作扩展后的字符串。
从一个五个字符的原始字符串中，最长的扩展字符串将为17个字符。
生成的扩展字符串可以由任何程序或SQL的“ORDERED BY”子句进行排序。
例如：
1A1A1   "    1A    1A    1"
11A11   "   11A   11"
1111A   " 1111A"
11111   "11111"
A1      "A    1"
A1B1    "A    1B    1"
A1C     "A    1C"
A2      "A    2"
A2B1    "A    2B    1"
A10     "A   10"
A10B1   "A   10B    1"
A11     "A   11"
AA1     "AA    1"
AB1     "AB    1"
AB2     "AB    2"
AB10    "AB   10"
ABC     "ABC"

伪代码：

// original = "section" string
exploded = ""
prevdigits = false
for ii from 1 to length(original) {
   ch = original[ii]
   if (ch is a digit) then {
      if not prevdigits then {
         token = ""
         prevdigits = true
      }
      token = token+ch
   } else { // letter
      if prevdigits then {
         exploded = exploded + spaces(5-length(token)) + token
         prevdigits = false
      }
      exploded = exploded + ch
   }
}

-Al.

抱歉我加了那个最后的评论。我刚刚弄明白了同样的事情，正准备回来更新我的代码。 - nkuebelbeck
0

我会在这些字符串后面加上空格，使其达到5个字符的长度，然后再进行基数排序。我们可以将所有符号视为字符进行比较。

    String[] array = {"A11", "AB1", "AB2", "AB3", "AB10"};

    int i, j, length;
    for (i = 0; i < array.length; i++) {
        length = array[i].length();
        for (j = length; j < 5; j++) {
            array[i] += " ";
        }
    }

    Arrays.sort(array);

    for (int k = 0; k<array.length; k++)
        System.out.println(array[k]);
0
这是我的代码。我相信它可以被简化，这是那种突然灵感来临时需要写下的代码。如果数字字符串超过5个字符，这段代码将无法正常工作...
更新：更少的丑陋。
private String buildPieceSortNumber(String pieceNumber){
    final int INTSPACES = 5;
    final String SPACE = " ";
    String explodedSection = "";        
    char[] charArray = pieceNumber.toCharArray();
    String ints = "";
    for(int i = 0;i < charArray.length;i++){
        if(Character.isDigit(charArray[i])){
            //add to the int string
            ints += charArray[i];
            //check if the next character in the array is a number
            int nextChar = i + 1;
            //make sure we don't go past the end of the string                
            if(nextChar < charArray.length){
                if(!Character.isDigit(charArray[nextChar])){
                    //end of numbers, take ints string, and add padding up to five positions
                    while(ints.length() < INTSPACES){
                        ints = SPACE + ints;
                    }
                    //add the int string to the end of the exploded string
                    explodedSection += ints;                        
                    //clear the int string 
                    ints = "";
                    }
            }else{
                //end of numbers, take ints string, and add padding up to five positions
                while(ints.length() < INTSPACES){
                    ints = SPACE + ints;
                }
                //add the int string to the end of the exploded string
                explodedSection += ints;
                //clear the int string 
                ints = "";
            }                
        }else{
            explodedSection += charArray[i];                                                            
        }
    }
    return explodedSection;
0

在将数据放入数据库之前，您真的需要对其进行排序吗？考虑让数据库为您完成这项工作。

假设您直接将值写入数据库。您的数据库可能允许您执行像我所做的操作一样的操作。在DB2中，要仅获取字母，我会将所有数字转换为空格，然后删除所有空格。相同的概念也适用于仅获取数字。

SELECT replace(translate(inp, @spaces, @digits),' ','') as alpha, 
       int(replace(translate(inp, @spaces, @letters),' ','')) as nbr,
       ....

虽然这可能是一种标准化的数据库方法，但您可能会质疑每次从表中检索数据时执行此计算。因此，最好在将数据写入表时进行计算。

INSERT INTO yourtable ( item, alpha, nbr, ..... )
     VALUES (inp,
             replace(translate(inp, @spaces, @digits),' ',''),
             int(replace(translate(inp, @spaces, @letters),' ','')),
             .....
            )

在我看来，这是更简单的逻辑，代码更少，更易于测试/调试，有助于减少缺陷风险，并且更容易维护。当然，根据您的数据库，您的情况可能会有所不同。但是这种方法似乎值得考虑。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接