逆向工程排序算法

Question

我得到了3种反求工程算法，并解释了它们是如何工作的。到目前为止，我已经得到了一种快速排序算法和一种气泡排序算法；但是我不知道这是什么算法。我明白快速排序和气泡排序是如何工作的，但我无法理解这个算法。我不知道变量是什么，我希望外面的人能告诉我这里发生了什么：

public static ArrayList<Integer> SortB(ArrayList<Integer> a)
{
    ArrayList<Integer> array = CopyArray(a);
    Integer[] zero = new Integer[a.size()];
    Integer[] one = new Integer[a.size()];
    int i,b;
    Integer x,p;
    //Change from 8 to 32 for whole integers - will run 4 times slower
    for(b=0;b<8;++b)
    {
        int zc = 0;
        int oc = 0;
        for(i=0;i<array.size();++i)
        {
            x = array.get(i);
            p = 1 << b;
            if ((x & p) == 0)
            {
                zero[zc++] = array.get(i);
            }
            else
            {
                one[oc++] = array.get(i);
            }
        }
        for(i=0;i<oc;++i) array.set(i,one[i]);
        for(i=0;i<zc;++i) array.set(i+oc,zero[i]);
    }
    return(array);
}

Answer 1

这是一个基类，限制在最不重要的8位。除非您将循环改为32次而不是8次，否则它不会完成排序。

每次迭代都处理一个位b。它通过移动p 1 left b times来准备一个名为b的掩码。这产生的幂为2- 1，2，4，8，.，或1，10,100,1000,10000，.二进制数。

对于每个位，将位b设置为1和0的原始数组中的元素数分为两个桶，称为one和zero。一旦分离结束，元素将被放回原始数组中，算法将继续进行下一次迭代。

这个实现使用的存储空间是原始数组的两倍，并且通过数组总共16次(在完整版本中是64次--一次用于读取，一次用于为每一位写入数据)。算法的渐近复杂度是线性的。

Answer 2

在我看来好像是点点滴滴的基数排序，但它似乎是向后排序。