1

您好我想了解基数排序的逻辑，我指的是维基百科的代码。这是接收数组的排序的排序函数，以及元素的数量。虽然代码运行得很好，但我无法理解代码的逻辑。在 while 循环中，我们首先初始化一个 10 位的桶数组，其中包含 1 的数量，以及数组的第一个和第二个索引的 2。但在那之后，很难理解它想要做什么。

static void sort(int a[],int n)
{
int i=0;
int m =a[0];
int b[]=new int[n];
int exp=1;


      for (i = 0; i < n; i++)
      {
        if (a[i] > m)
          m = a[i]; 
      }

      while (m / exp > 0)
      {
        int bucket[] =new int[10];
        for (i = 0; i < n; i++)
          bucket[a[i] / exp % 10]++;


        for (i = 1; i < 10; i++)
          bucket[i] += bucket[i - 1];
        for (i = n - 1; i >= 0; i--)
          b[--bucket[a[i] / exp % 10]] = a[i];
        for (i = 0; i < n; i++)
          a[i] = b[i];
        exp *= 10;

          System.out.println("\nPASS   : ");
          for(int c:a){
        System.out.print(c+",");
    }
          System.out.println();
      }

}

谁能帮我这个？谢谢

4

1 回答 1

2

即使您知道基数排序的工作原理，这段代码也需要花费一些精力来理解。首先理解基数排序的抽象描述比尝试从这段代码中对其进行逆向工程更容易。

关于代码的一些技术观察：

  • 外部循环控制exp从 1,10,100... 到 10 的连续幂，并确定我们当前排序的数字的哪个十进制数字。
  • 实际排序到桶中是两次。第一个内部循环计算每个桶的计数，第三个将数字分布到各个桶中（a[]在每个桶中和每个桶内从 n 到 1。）
  • 存储桶表示为辅助b[]数组中的间隔（其偏移量在第二个内部循环中根据第一个内部循环的存储桶计数预先计算）
  • 在第二个循环之后bucket[d]是区间上端（不包括）的索引，该区间将存储活动数字（我们排序的数字）为 的数字d。桶间隔从该端向下填充。
于 2012-11-29T21:57:00.427 回答