0

我正在尝试对“随机”整数数组进行基数排序。radix_sort 函数给了我段错误错误。我检查了每个 for 循环，它们似乎都没有超出范围，所以我的假设是问题可能出在数组指针上，但我似乎无法在网络上找到任何有助于解决任何此类问题的源信息。使用带有 -std=c99 标志的 GCC 编译

#include <stdio.h>
#include <stdlib.h>

#define LEN 1000
#define BYTES 4
#define BINS 256

void create_lst();
void int_radix_sort();
void radix_sort(int);

long data[LEN];
long temp[LEN];

int main(int argc, char * * argv) {
  create_lst();
  int_radix_sort();

  return 0;
}
void create_lst() {
  for (int i = 0; i < LEN; i++) {
    srand(rand());
    data[i] = rand();
  }
  return;
}
void int_radix_sort() {
  for (int i = 0; i < BYTES; i++) {
    radix_sort(i);
  }
  return;
}
void radix_sort(int byte) {
  long map[BINS], count[BINS];
  long *src_p, *dst_p;

  if((byte%2) == 0){
    src_p = data;
    dst_p = temp; 
  } else {
    src_p = temp;
    dst_p = data;
  }
  // Count
  for(int i = 0; i < LEN; i++)
    count[(src_p[i] >> (byte*8)) & (BINS-1)]++;
  // Map
  map[0]=0;
  for(int j = 1; j < BINS; j++)
    map[j] = count[j-1] + count[j-1];
  // Move
  for(int k = 0; k < LEN; k++)
    dst_p[map[(src_p[k] >> (byte*8)) & (BINS-1)]++] = src_p[k];
  return;
}

编辑：更多信息 - 当我通过调试器运行程序时，我发现问题出在最后一个循环上（使用 K 变量）

4

2 回答 2

3

count数组 in未初始化，它的radix_sort值用于创建 inmap的值，最后（参见// Move）用于索引dst_p，然后是 BOOM。

在你修复初始化它们之后，你最终得到1954in map[1]，这对于 来说太大了dst_p，所以现在你正在研究一个算法问题。尝试添加一些跟踪打印语句来解决您的问题。或者进入调试器（gdb在 Linux 上）并单步执行您的程序以验证所有步骤是否符合预期。

于 2013-05-27T16:48:49.663 回答
1 
for(int j = 1; j < BINS; j++)
    map[j] = count[j-1] + count[j-1];

是错的。您想map[j]保存前一个插槽中元素的累积数量，因此应该是

for(int j = 1; j < BINS; j++)
    map[j] = map[j-1] + count[j-1];
         //  ^^^
         //  add the number of items in bin j-1 to the number of items in previous bins
于 2013-05-27T17:37:22.140 回答