基数排序算法

Question

我被分配了一些算法来进行逆向工程。下面的算法是基数排序，但我非常困惑代码中实际发生了什么。

我对算法很陌生，不确定代码如何对数组元素进行排序。我不知道比特（bits）与算法有何关系以及掩码(mask)是什么。以下是代码：

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

- user3185731

---

避免使用Integer，它们速度慢且浪费内存。请使用int。 - Has QUIT--Anony-Mousse

Answer 1

算法是你开始学习编程的地方！

要查看未记录的代码段执行的操作，您可能需要采用伪语言将工作转换为英语数学语句。

例如，您注意到此片段仅适用于8位数字（位上的外部循环）。粗略描述是，根据位“位”的零或一，将数组元素“排序”成两个桶-从最不重要的位置开始。然后重新排列原始数组，“ones”在“zeros”之前..这应该按照从大到小的顺序排序数组。

您最好查找基数排序算法，并从其中开始，而不是从代码开始。

- ErstwhileIII

Answer 2

你的算法适用于8位数字，你一次只查看一个位。以下是一个更易理解的例子，使用十进制而不是二进制。

Sort on 1s:    771 721 822 955 405   5 925 825 777  28 829
Sort on 10s:   405   5 721 822 925 825  28 829 955 771 777
Sort on 100s:    5  28 405 721 771 777 822 825 829 925 955

在我们按中间数字排序后，可以观察到数字是按它们的最后两位排序的。 在我们按最高有效数字排序后，这些数字就完全排好序了。

对于二进制也是如此。 我们用来排序的桶的数量与我们在桶或计数排序期间使用作为排序键的数字的基数相同。 "基数"是数字的底数的同义词，因此名称为“基数排序”。 在你的例子中，该数字为2。

- Jobs

Answer 3

/*try this iterative method and 100% working*/
    #include<stdio.h>
    #include<math.h>
    int sort();
    int display();
    long int a[20],n;
    int main(){
    int i;
    printf("enter the size:");
    scanf("%d",&n);
    printf("\nenter the array elements\n");
          for(i=0;i<n;i++){scanf("%d",&a[i]);}
             sort();
   return 0;
          }

int sort()
{
int p=0,rad[20],q,s=0,i=0;
int k1,k2,t; 
while(p<=3)
     {
q=0;
          while(q<=9)
               {
                 i=0;
          while(a[i]!='\0')
               {
                 t=pow(10,(p+1));
                 k1=a[i]%t;
                 k2=k1/pow(10,p);

          if(k2==q) {rad[s]=a[i];s++;}
             i++;
                }
         q++;
                }
 s=0;
 printf("\n sort for %dth\n",p);
 for(i=0;i<n;i++){a[i]=rad[i];}
 printf("\n");
  display();
 p++;
       }
return 0;
       }    

int display(){
int i=0;
while(a[i]!='\0')
 {
printf("%d\t",a[i]);
i++;
 }
return 0;
              }

- Goutham nagraj

---

在输出排序中，0、1、2、3、4 表示个位、十位、百位和千位。 - Goutham nagraj

Answer 4

一个掩码，或位掩码，被用于“关闭”除了那些通过掩码被“允许”“看到”的每个位。 0 过滤它们要与之AND的位， 1 允许该位通过。常见用法是隔离整数数据类型的字节大小部分：

00000000 11111111 00000000 00000000
& // Boolean AND
10010101 10010101 10010101 10010101
yields
00000000 10010101 00000000 00000000

- Floegipoky

---

虽然这些信息是正确的，但它并没有涉及到如何辨别或描述一组代码所实现的算法的核心问题。 - ErstwhileIII

@floegipoky，没错，这个“答案”并没有回答完整的问题，但它确实回答了OP说的那部分，“我不确定[...]什么是掩码”。 - Solomon Slow