0

我在使用计数排序按字母顺序对名称进行排序时遇到问题，例如，我想按字母顺序排序并添加数字输入0001 Alex Smith, Gregory John, Alex Smith, Adam Richard, Alex Ryan。输出应按以下顺序：

亚当·理查德·
亚历克斯·瑞恩·亚历
克斯·史密斯
格雷戈里·约翰

到目前为止我的代码：

public class Names 
{
    //private static int[] c;

 public ArrayList<String> getUserInput()
{
        ArrayList<String> names = new ArrayList<String>(); 
    Scanner in = new Scanner(System.in);
    while (in.hasNext()) 
     {
         names.add(in.next());  
        System.out.println(names); 
     }
      in.close();
    return names;
}
 private static CountingSort(int A[], int B[], int k[])
{
    int i;
    int C[0];
    for(i = 0; i <= k; i++){
        C[i]=0;
    }

    for(int j=1; j <= A.length; ){
        C[A[j]] = C[A[j]] + 1;
    }//C[i] now contains numbers of elements equals to i
    for(int i=1; i < k; i++){
        C[i] = C[i] + C[i - 1];

    }
    for(int j = A.length; j--){
    B[C[A[j]]] = A[j];
    C[A[j]] = C[A[j]] - 1;   
   }
}
}
4

2 回答 2

2

准备数据

一个。使每个字符串的长度相等。在每个字符串的末尾添加“*”以使所有长度相等。

Modified Data — [‘a*’, ‘bd’, ‘cd’, ‘ab’, ‘bb’, ‘a*’, ‘cb’]

湾。通过将位置值分配给字母，将修改后的数据字符串转换为数字。az 到 1-26 和 * 到 0。所以这变成了二维数组。

Converted Data — [[1,0],[2,4],[3,4],[1,2],[2,2],[1,0],[3,2]]

计数排序

  1. 创建 n 维的计数数组，其中 n = 最长字符串的长度（在本例中为 2），并且每个维度中的列数 =“转换数据”中的最大值（在本例中为 4）+1（为“*”添加）。因此，创建了一个 5x5 的计数数组。

例如——如果字符串的最长长度是 5 和最高字符“f”，那么将创建一个 7x7x7x7x7 的数组。

就像普通的计数数组一样，存储基于“转换数据”的值。例如，对于 [1,0]，存储的值为 2。 计数数组

  1. 从 [0,0] 一直到 [4,4] 累积这个 n 维数组。

  2. 现在类似地使用带有计数数组的“转换数据”来确定每个字符串在排序数组中的位置。例如。— [1,0] (a*) 位置为 2。类似地，在确定位置后，从 count 数组中的该值中减去 1。因此 Count 数组中 [1,0] 处的值变为 1。类似地，[2,4] (bd) 的位置在排序数组中为 5。

https://playcode.io/475393

于 2019-12-05T18:18:33.583 回答
0

计数排序是这个问题的错误排序算法。计数排序算法旨在对固定范围内的整数值进行排序，因此不能应用于对字符串进行排序。

另一方面，您可以使用基数排序来解决这个问题。基数排序通过一次对输入的一个数字或字符进行排序来工作，它非常适合对字符串进行排序。基数排序有两种一般风格 - 最高有效位基数排序和最低有效位基数排序。基数排序的 MSD 风格不太让人想起计数排序，但 LSD 基数排序通过一次使用一个字符计数排序来工作。如果您真的必须使用计数排序，我建议您研究 LSD 基数排序作为一个选项。

于 2015-08-26T19:34:04.913 回答