基数排序分解

Question

这是一个简单的问题，我试图找出基数排序，我给了这个代码，但不能退出弄清楚为什么我们需要W，似乎它使用的是给定的单词的长度，但是，我想知道如果单词不固定那么什么?

和为什么我们需要扩展ASCII大小?

为什么我们需要计算频率计数和计算累计?

我们技术上不需要这两个for循环，对吧?

感谢

public static void sort(String[] a, int W) 
{
    int N = a.length;
    int R = 256;   // extend ASCII alphabet size
    String[] aux = new String[N];
    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++)
            count[a[i].charAt(d) + 1]++;
        // compute cumulates
        for (int r = 0; r < R; r++)
            count[r+1] += count[r];
        // move data
        for (int i = 0; i < N; i++)
            aux[count[a[i].charAt(d)]++] = a[i];
        // copy back
        for (int i = 0; i < N; i++)
            a[i] = aux[i];
    }
}

Answer 1

但不明白为什么我们需要W，似乎它使用的是W但是，我想知道这些词是否没有固定，然后呢?

如果字符串较长，则其余字符将不参与排序。如果字符串更短，那么我相信你会得到一个IndexOutOfBoundException

和为什么我们需要扩展ASCII大小?

正如Blorgbeard所提到的，这指的是"扩展的"ASCII集。ASCII在127之后没有定义。"扩展"的ASCII码包括0到255的字符。

为什么我们需要计算频率计数和计算累计?

这是对第d个字符上的字符串进行排序。实际上，前三个部分执行排序，最后一个部分复制部分排序的数组。

我们技术上不需要这两个for循环，对吧?

从技术上讲，您可以找到另一种方法来对d字符上的字符串进行排序，但这似乎很好地完成了这项工作。