基数排序算法 [英] Radix Sort Algorithm

问题描述

我一直在考虑一些算法进行逆向工程。下面的算法是基数排序，但我很困惑什么是真正发生在code。

我是新来的算法和我不能确定如何code排序数组中的元素。我不知道什么位都与算法，什么口罩。这里是code：

 的ArrayList＆LT;整数GT;阵列= CopyArray（一）;
    整数[] zerobucket =新的整数[a.size（）];
    整数[] onebucket =新的整数[a.size（）];
    INT I，位;
    整型元素，面膜;

    对（位= 0;位＆LT; 8; ++位）{
        INT ZC = 0;
        INT OC = 0;

        对于（i = 0; I＆LT; array.size（）; ++ I）{
            元素= array.get（ⅰ）;
            掩模= 1＆其中;＆其中;位;
            如果（（元素和放大器;面罩）== 0）{
                zerobucket [ZC ++] = array.get（ⅰ）;
            } 其他 {
                onebucket [OC +] = array.get（我）;
            }
        }
        对于（i = 0; I＆LT; OC ++ I）array.set（我，onebucket [I]）;
        对于（i = 0; I＆LT; ZC ++ I）array.set（1 + OC，zerobucket [I]）;
    }
    返回（阵列）;
 

解决方案

算法是，你应该开始学习编程！

要看看无证件code呢，你可能需要采取伪语言把工作分为英语数学声明。

例如，您注意，这个段应只对8位数字（对位外循环）。粗略的描述是数组元素的排序为根据位置的位的位是0或1两桶水 - 开始在租赁显著位置位。原来的数组，然后重新排序10在来之前..这应当责令该阵列从最大到最小。

您将得到更好的服务来查找基数排序算法，并开始了，而不是开始code。

I have been given some algorithms to reverse engineer. The algorithm below is a radix sort, but I am very confused about what is actually happening in the code.

I'm new to algorithms and am unsure how the code sorts elements in an array. I'm not sure what bits have to do with the algorithm and what a mask is. Here is the code:

    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);

解决方案

Algorithms are where you should start learning about programming!

To see what an undocumented piece of code does, you may need to adopt a pseudo-language to put the work into an english mathematics statement.

For example, you note that this snippet should only work for 8-bit numbers (the outer loop on bit). The rough description is that the array elements are "sorted" into two buckets depending on whether the bit in position "bit" is a zero or a one -- starting with the bit in the lease significant position. The original array is then reordered with "ones" coming before "zeros" .. which should order the array from largest to smallest.

You would be well served to look up radix sort algorithms, and start with that rather than starting with code.

这篇关于基数排序算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！