逆向工程排序算法

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

对我来说看起来像是逐位基数排序，但它似乎是向后排序。

Answer 2

这是一个Radix Sort，限于最低有效八位。它不会完成排序，除非您将循环更改为 32 次而不是 8 次。

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

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

此实现使用的存储空间是原始数组大小的两倍，总共遍历数组 16 次（完整版本中为 64 次 - 一次用于读取数据，一次用于写入每个位的数据).算法的渐近复杂度是线性的。

逆向工程排序算法

Reverse Engineer Sorting Algorithm

java

arrays

sorting

algorithm

reverse-engineering