实现LSD基排序

Question

我希望对这个LSD基排序实现进行代码回顾。我已经推出了自己的，并实现了计数排序以及。我觉得我选择的一些数据结构可以改进。例如，我的List<List<char[]>>有点粗俗，它的内部摆弄比我认为的复杂得多。

public class LSDSorting {

private static final int DIGIT_RANGE = 5;


public static void main(String[] args) {
    char[][] toSort = new char[][]{"0123".toCharArray(), "1233".toCharArray(), "1212".toCharArray(), "1111".toCharArray(), "4444".toCharArray()};

    int LSD_INDEX = toSort[0].length - 1;
    char[][] sorted = lsdSort(toSort, LSD_INDEX);

    for (char[] str: sorted) {
        System.out.println(String.valueOf(str));
    }
}

private static char[][] lsdSort(char[][] toSort, int d) {
    if (d < 0) {
        return toSort;
    }

    char[][] sortedOnD = runCountingSort(d, toSort, DIGIT_RANGE);
    return lsdSort(sortedOnD, d-1);
}


private static char[][] runCountingSort(int d, char[][] toSort, int range) {
    List<List<char[]>> idx = new ArrayList<>();
    for (int i = 0; i < range; i++) {
        idx.add(i, new ArrayList<char[]>());
    }

    for (int i = 0; i < toSort.length; i++) {
        int currVal = Character.getNumericValue(toSort[i][d]);
        List<char[]> currList = idx.get(currVal);
        if (currList == null) {
            currList = new ArrayList<>();
            idx.add(currVal, currList);
        }
        currList.add(toSort[i]);
    }

    char[][] result = new char[toSort.length][toSort[0].length];
    int currIdx = 0;
    for (int i = 0; i < idx.size(); i++) {
        for (char[] str : idx.get(i)) {
            result[currIdx] = str;
            currIdx++;
        }
    }
    return result;
}
}

Answer 1

排序的一个重要方面是它必须是快速的，而且它不会填满整个堆空间。这就是为什么在合并排序之前更喜欢快速排序的原因。

我认为你的代码占用了更多的内存。

• 您不需要在lsdSort中使用递归，我认为它使它更复杂，效率更低。对于长字符串，您也可能会遇到意外的堆栈溢出异常。
• 在每次迭代中，您都要为所需的一切创建新的实例。字符矩阵和列表列表。如果丢弃递归，则可以在每次迭代中重用相同的副本。
• 当您知道List的大小并且没有与任何其他方法交互时，不要使用它或它的任何实现。(您可能知道有一种开销)
• List<char[]> currList = idx.get(currVal);后面跟着空检查似乎对您的代码没有任何意义？List.get()

我将如何做到这一点:到目前为止，我看到的最好的实现是来自Robert的一本书。

/**  
 * Rearranges the array of W-character strings in ascending order.
 *
 * @param a the array to be sorted
 * @param W the number of characters per string
 */
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];
    }
}

我认为你使用列表的想法是好的。而且可能看起来更快，因为通过跳过累积计数，可以减少一次迭代次数。不过，它又干净又简单。

LSD.java