java - 基数排序算法

Question

我得到了一些逆向工程算法。下面的算法是基数排序，但我对代码中实际发生的事情感到非常困惑。

我是算法新手，不确定代码如何对数组中的元素进行排序。我不确定哪些位与算法有关以及掩码是什么。这是代码:

    ArrayList<Integer> array = CopyArray(a);
    Integer[] zerobucket = new Integer[a.size()];
    Integer[] onebucket = new Integer[a.size()];
    int i, bit;
    Integer element, mask;

    for (bit=0; bit<8; ++bit) {
        int zc = 0;
        int oc = 0;

        for(i=0; i<array.size(); ++i) {
            element = array.get(i);
            mask = 1 << bit;
            if ((element & mask) == 0) {
                zerobucket[zc++] = array.get(i);
            } else {
                onebucket[oc++] = array.get(i);
            }
        }
        for(i=0; i<oc; ++i) array.set(i,onebucket[i]);
        for(i=0; i<zc; ++i) array.set(i+oc,zerobucket[i]);
    }
    return(array);

Answer 1

算法是您学习编程的起点!

要查看一段未记录的代码的作用，您可能需要采用伪语言将其放入英语数学语句中。

例如，您注意到此代码段应仅适用于 8 位数字(位外循环)。粗略的描述是，根据位置“bit”中的位是零还是一，数组元素被“排序”到两个桶中——从租约有效位置的位开始。然后将原始数组重新排序为“0”之前的“1”..这应该从最大到最小对数组进行排序。

您最好查找基数排序算法，然后从它开始而不是从代码开始。