关于 Java 基数排序实现的解释

Question

我正在阅读和学习基数排序的 Java 实现，如下所示。如果有人能阐明 pointTo、index 和 globalPtr 的逻辑含义，那就太好了。

https://www.hackerrank.com/challenges/string-similarity/editorial

private void radixSort0() {
    globalPtr = 0;
    Arrays.fill(bucketHead, -1);
    Arrays.fill(next, -1);

    for (int i = 0; i < n; i++) {
        int value = nr0[index[i]];
        if (bucketHead[value] == -1) bucketHead[value] = bucketTail[value] = globalPtr;
        else bucketTail[value] = next[bucketTail[value]] = globalPtr;
        pointTo[globalPtr++] = index[i];
    }

    int ptr = 0;
    for (int i = 0; i < M; i++)
        for (int j = bucketHead[i]; j != -1; j = next[j])
            index[ptr++] = pointTo[j];
}

Answer 1

import java.io.*;
import java.util.*;

public class St {
    public static int calculate(String s){
        char[]arr=s.toCharArray();
        int length=arr.length;
        int count=length;
        for(int i=1;i<length;i++){
            int len=length-i;
            int j=0;
            for(;j<len;j++)
                if(arr[j]!=arr[j+i]){
                    break;
                }
            count+=j;
        }
        return count;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner( System.in );
        int n=scanner.nextInt();
        for(int i=0;i<n;i++){
            String s=scanner.next();
            System.out.println(calculate(s));
        }
    }
}

由于超时，它几乎通过了除最后两个之外的所有测试用例希望我的工作有助于愉快的编码..

Answer 2

这个radixSort0()不是完全基数排序。如果您的目标是了解基数排序，请查看其他地方。
在这两个（不必要重复的）radixSort 方法中，int[] next 用于建立单向链表——使用索引而不是引用，使用 -1 而不是 null。（您可以 而不是 只需将 next[some_index_depending_on value] 设置为 index[i] - 不会有列表。） int[] pointTo 可能更具有描述性地命名为 value。将 next&value 视为链接列表，以具有两个数组类型数据成员的实例表示，作为具有成员 next&value 的实例数组的替代方案。 globalPtr 是 that/those array/s 中尚未分配的最小索引。

（后面的代码中明显缺少注释是因为我不理解为什么有人应该尝试使用它构造后缀数组，或者这些代码片段对实现该目标有何贡献：随时纠正和修改.)
甚至不考虑测试，Java 处理这个问题的方法可能是

private void radixSortStep(int[]nr) {
    List<Integer> value[] = new List[M];
    for (int i = 0; i < value.length; i++)
        value[i] = new ArrayList<Integer>(0);

    for (int i: indexes)
        value[nr[i]].add(i);

    int ptr = 0;
    for (int i = 0; i < M; i++)
        for (int val: value[i])
            indexes[ptr++] = val;
}

（关于 M（设置为 n+1）和 nr1（初始化条目未从等级复制到 n，而不是 -1） )

关于 Java 基数排序实现的解释

explanation about a Java implementation of radix sort

java

algorithm

sorting

radix-sort