Radix使用队列排序

4 回答

• 1

  我已经修改了你的队列了一下 . 为了更好地理解代码，我使用front和rear作为全局变量 .

  typedef struct queue *queue_ptr;
          struct queue {
                 int data;
                 queue_ptr next;
          };
  queue_ptr front[10], rear[10];  /* For base 10, The 11th queue is not needed */
  

  所以添加到队列的操作就变成了

  void add_queue(int i, int data) {
          queue_ptr tmp;
  
          tmp = (queue_ptr) malloc(sizeof(*tmp));
          tmp->next = NULL;
          tmp->data = data;
          if (front[i]) {
                  rear[i]->next = tmp;
          } else {
                  front[i] = tmp;
          }   
          rear[i] = tmp;
  }
  

  并添加从队列中删除的操作（也返回数据）

  int delete_queue(int i) {
          int data;
          queue_ptr tmp;
  
          tmp = front[i];
          if (!tmp) {
                  return -1;  /* So that we can check if queue is empty */
          }   
          data = tmp->data;
          front[i] = tmp->next;
          free(tmp);
          return data;
  }
  

  所以现在我们可以实现基数排序 . 使用实际数字而不是单个数字将数据移动到队列中可能更容易 . 请注意，如果您可以修改测试数组* arr，则不需要第11个队列，并且您的radix_sort函数可能如下所示：

  void radix_sort(int *arr, const int size) {
          int i, j, k, radix, digits, tmp;
  
          if (size < 1) {
                  return;  /* don't do anything if invalid size */
          }
  
          /* get the number of digits */
          for (digits = 0, radix = 1; arr[0] >= radix; digits++, radix *= 10);
  
          /* perform sort (digits) times from LSB to MSB */
          for (i = 0, radix = 1; i < digits; i++, radix *= 10) {
                  /* distribute into queues */
                  for (j = 0; j < size; j++) {
                          add_queue((arr[j] / radix) % 10, arr[j]);
                  }
                  /* take them out from each queue to the original test array */
                  for (j = 0, k = 0; j < 10; j++) {
                          for (tmp = delete_queue(j); tmp != -1;\
                               tmp = delete_queue(j), k++) {
                                  arr[k] = tmp;
                          }
                  }
          }
  }
  

  最后你可以通过调用radix_sort（your_array，your_array_size）来测试，完整的代码是

  #include <stdio.h>
  #include <stdlib.h>
  
  typedef struct queue *queue_ptr;
          struct queue {
                 int data;
                 queue_ptr next;
          };
  
  queue_ptr front[10], rear[10];  /* For base 10, The 11th queue is not needed */
  
  void add_queue(int i, int data) {
          queue_ptr tmp;
  
          tmp = (queue_ptr) malloc(sizeof(*tmp));
          tmp->next = NULL;
          tmp->data = data;
          if (front[i]) {
                  rear[i]->next = tmp;
          } else {
                  front[i] = tmp;
          }
          rear[i] = tmp;
  }
  
  int delete_queue(int i) {
          int data;
          queue_ptr tmp;
  
          tmp = front[i];
          if (!tmp) {
                  return -1;  /* So that we can check if queue is empty */
          }
          data = tmp->data;
          front[i] = tmp->next;
          free(tmp);
          return data;
  }
  
  void radix_sort(int *arr, const int size) {
          int i, j, k, radix, digits, tmp;
  
          if (size < 1) {
                  return;  /* don't do anything if invalid size */
          }
  
          /* get the number of digits */
          for (digits = 0, radix = 1; arr[0] >= radix; digits++, radix *=10);
  
          /* perform sort (digits) times from LSB to MSB */
          for (i = 0, radix = 1; i < digits; i++, radix *= 10) {
                  /* distribute to queues */
                  for (j = 0; j < size; j++) {
                          add_queue((arr[j] / radix) % 10, arr[j]);
                  }
                  /* take them out from each queue to the original test array */
                  for (j = 0, k = 0; j < 10; j++) {
                          for (tmp = delete_queue(j); tmp != -1;\
                               tmp = delete_queue(j), k++) {
                                  arr[k] = tmp;
                          }
                  }
          }
  }
  
  int main(void) {
          int i;
          int a[5] = {133, 34, 555, 111, 12},
              b[12] = {1, 1, 1, 4, 5, 6, 7, 8, 9, 11, 11, 12};
  
          radix_sort(a, 5);
          radix_sort(b, 5);
  
          for (i = 0; i < 5; i++) {
                  printf("%d ", a[i]);
          }
          printf("\n");
  
          for (i = 0; i < 12; i++) {
                  printf("%d ", b[i]);
          }
          printf("\n");
  
          return 0;
  }
  

  而输出是

  12 34 111 133 555
  1 1 1 4 5 6 7 8 9 11 11 12
  

  回复于 2024-04-30T08:58:32+08:00
• 3

  这里有一些很好的信息 . 在更高的层次上，调试代码将很困难，因为它比它需要的更复杂 . 下面是一个使用C以更惯用的方式表达算法的不同代码 .

  总的来说，在代码方面，通常更少：简单就是你的朋友 . 这里显示的功能：

  • 循环单列表队列 . 队列是指向列表尾节点的指针 . 有了这个，追加和连接是快速的恒定时间操作 .

  • 逻辑，可重用的功能分解 .

  • 只有大约80 SLOC，包括一个简单的测试 . 排序功能是18 SLOC .

  • 轻微测试 .

  这是排序：

  // Radix sort the given queue.
  void sort(QUEUE *queue)
  {
    unsigned i, j, div;
    QUEUE queues[RADIX], accum;
  
    // Handle case of nothing to sort.
    if (*queue == NULL) return;
  
    // Accumulator queue initially holds unsorted input.
    accum = *queue;
  
    // Make one pass per radix digit.
    for (i = 0, div = RADIX; i < MAX_DIGITS; i++, div *= RADIX) {
  
      // Clear the radix queues.
      for (j = 0; j < RADIX; j++) queues[j] = NULL;
  
      // Append accumulator nodes onto radix queues based on current digit.
      NODE *p = accum, *p_next = p->next;
      do {
        // Save p->next here because append below will change it.
        p = p_next; p_next = p->next;
        append_node(&queues[p->val / div % RADIX], p);
      } while (p != accum);
  
      // Gather all the radix queues into the accumulator again.
      for (accum = NULL, j = 0; j < RADIX; j++) cat(&accum, queues[j]);
    }
    // Accumulator now holds sorted input.
    *queue = accum;
  }
  

  其余的：

  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  
  #define RADIX 10
  #define MAX_DIGITS 9
  
  // Node and circular queue. A queue is either null or a pointer to the _tail_ node.
  typedef struct node_s {
    struct node_s *next;
    unsigned val;
  } NODE, *QUEUE;
  
  // Make a new node with given value.
  NODE *new_node(unsigned val)
  {
    NODE *node = calloc(1, sizeof *node);
    // Must trap null return value here in production code!
    node->val = val;
    return node;
  }
  
  // Append given node to the tail of a queue.
  void append_node(QUEUE *queue, NODE *node)
  {
    NODE *tail = *queue;
    if (tail) {
      node->next = tail->next;
      tail->next = node;
    }
    else {
      node->next = node;
    }
    *queue = node;
  }
  
  // Concatenate the second queue onto the tail of the first. 
  // First queue is changed (because it's a pointer to a tail node).
  void cat(QUEUE *a, QUEUE b_tail)
  {
    NODE *a_tail, *a_head;
  
    if (b_tail == NULL) return;
    a_tail = *a;
    if (a_tail) {
      a_head = a_tail->next;
      a_tail->next = b_tail->next;
      b_tail->next = a_head;
    }
    *a = b_tail;
  }
  // Sort code above goes here if you're compiling it.
  // And test main goes here.
  

  一个小测试主要：

  int main(void)
  {
    int i;
    unsigned data[] = { 98, 111, 42, 1111, 21 , 997, 0, 99999, 20903};
  
    // Make a queue from data.
    QUEUE a = NULL;
    for (i = 0; i < sizeof data / sizeof data[0]; i++)
      append_node(&a, new_node(data[i]));
  
    sort(&a);
  
    // Print the circular list.
    NODE *p = a;
    do {
      p = p->next;
      printf("%u\n", p->val);
    } while (p != a);
  
    return 0;
  }
  

  回复于 2024-04-30T08:58:32+08:00
• 0

  免责声明：我不会将此作为练习留给您 .

  当你发现你自己复制粘贴的东西不止一次停下来思考：必须有一个模式 .

  你的switch语句有很多复制粘贴 . 在 case 1: 你有一条线：

  queue[1]->frontp = queue[0]->rearp;
  

  我猜它应该是：

  queue[1]->frontp = queue[1]->rearp;
  

  如果你重新考虑了这段代码，你可能会更容易看到这个？

  用以下内容替换整个switch语句怎么样？

  int leastSignificantDigit = curNum%10;
  
  if(queue[leastSignificantDigit]->size == 0){
      queue[leastSignificantDigit]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
      queue[leastSignificantDigit]->frontp = queue[leastSignificantDigit]->rearp;
  } else {
      queue[leastSignificantDigit]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
      queue[leastSignificantDigit]->rearp = queue[leastSignificantDigit]->rearp->restp;
  }
  ++(queue[leastSignificantDigit]->size);
  queue[leastSignificantDigit]->rearp->element = curNodep->element;
  queue[leastSignificantDigit]->rearp->restp = NULL;
  radixSort(curNodep->restp, queue, size);
  

  回复于 2024-04-30T08:58:32+08:00
• 0

  我在第一个代码示例中看到的问题是

  curNum = curNodep->element.key

  curNum总是有完整的数字，而switch语句总是这样做 curNum % 10 ，而这只是测试最后一位数 .

  在你的递归解决方案中（递归不是问题）你必须传递一个参数来知道它必须处理的数字 .

  我知道这种技术是沉浸式的 .

  如果您看到在答案结尾处放置的样本，您可以看到最后一个数字是orderer，您可以更改输入样本以更好地了解这一点 . 使用较小的最后一个数字添加大数字，例如'901'，查看结果 .

  对不起我的英语不好...

  回复于 2024-04-30T08:58:32+08:00