c - C 中 10^6 数组的基数排序

Question

这个问题已经有答案了:

Understanding memory allocation, test program crashing (4 个回答)

已关闭 8 年前。

我有这段代码，它在处理过程中崩溃了。系统给出消息“filename.exe 停止工作。这里出了什么问题？我将数组声明为全局数组，以便能够拥有如此大量的元素，但它仍然不起作用。

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

#define MAX 1000000
#define SHOWPASS

void print(int *a, int n) {
 int i;
 for (i = 0; i < n; i++)
  printf("%d\t", a[i]);
}

void radix_sort(int *a, int n) {
 int i, b[MAX], m = 0, exp = 1;
 for (i = 0; i < n; i++) {
  if (a[i] > m)
   m = a[i];
 }

 while (m / exp > 0) {
  int box[10] = { 0 };
  for (i = 0; i < n; i++)
   box[a[i] / exp % 10]++;
  for (i = 1; i < 10; i++)
   box[i] += box[i - 1];
  for (i = n - 1; i >= 0; i--)
   b[--box[a[i] / exp % 10]] = a[i];
  for (i = 0; i < n; i++)
   a[i] = b[i];
  exp *= 10;

#ifdef SHOWPASS
  printf("\n\nPASS   : ");
  print(a, n);
#endif
 }
}
int arr[MAX];
int main() {
 //int arr[MAX];
 int i, num;

 printf("\nEnter total elements (num < %d) : ", MAX);
 scanf("%d", &num);

 printf("\ncreate array : ");
 for (i = 0; i < num; i++)
  arr[i]=rand()%10;

 printf("\nARRAY  : ");
 print(&arr[0], num);

 radix_sort(&arr[0], num);

 printf("\n\nSORTED  : ");
 print(&arr[0], num);

 return 0;
}

这是我尝试过的另一个代码，这次我使用了 malloc。但在开始排序之前它仍然崩溃。如果元素数量 <100000，一切都很好。

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

#define MAX 1000000
#define SHOWPASS

void print(int *a, int n) {
 int i;
 for (i = 0; i < n; i++)
  printf("%d\t", a[i]);
}

void radix_sort(int *a, int n) {
 int i, b[MAX], m = 0, exp = 1;
 for (i = 0; i < n; i++) {
  if (a[i] > m)
   m = a[i];
 }

 while (m / exp > 0) {
  int box[10] = { 0 };
  for (i = 0; i < n; i++)
   box[a[i] / exp % 10]++;
  for (i = 1; i < 10; i++)
   box[i] += box[i - 1];
  for (i = n - 1; i >= 0; i--)
   b[--box[a[i] / exp % 10]] = a[i];
  for (i = 0; i < n; i++)
   a[i] = b[i];
  exp *= 10;

#ifdef SHOWPASS
  printf("\n\nPASS   : ");
  print(a, n);
#endif
 }
}

int i, num;
int main() {

int* arr = (int*)malloc(MAX * sizeof(int));
int i;

 printf("\ncreate array : ");
 for (i = 0; i < MAX; i++)
  arr[i]=rand()%10;

 printf("\nARRAY  : ");
 print(&arr[0], MAX);

 radix_sort(&arr[0], MAX);

 printf("\n\nSORTED  : ");
 print(&arr[0], MAX);
free(arr);
 return 0;
}

Answer 1

错误在这里:

 int i, b[MAX], m = 0, exp = 1;

在某些(如果不是大多数)系统上，在堆栈上分配一个巨大的(100 万个 int )数组是不可能的。

您应该malloc临时数组并仅分配排序所需的大小，即n * sizeof(int)。

另一个问题是:您的 radix_sort 无法处理负数。

不太重要但值得一提:您的实现并不稳定。对于简单的 int 数组来说不是问题，但对于较大的结构可能不正确。

此外，您的代码效率很低:您使用除法和模 10。使用移位和掩码会快得多。

这是大型数组的更有效实现:

#include <limits.h>
#include <string.h>
#include <stdlib.h>

static void radix_sort(int *a, size_t size) {
    size_t counts[sizeof(*a)][256] = {{ 0 }}, *cp;
    size_t n, i, sum;
    unsigned int *tmp, *src, *dst, *aa;

    dst = tmp = malloc(size * sizeof(*a));
    src = (unsigned int *)a;
    for (i = 0; i < size; i++) {
        unsigned int v = src[i] + (unsigned int)INT_MIN;
        for (n = 0; n < sizeof(*a) * 8; n += 8)
            counts[n >> 3][(v >> n) & 255]++;
    }
    for (n = 0; n < sizeof(*a) * 8; n += 8) {
        cp = &counts[n >> 3][0];
        if (cp[0] == size) continue;
        for (i = sum = 0; i < 256; i++)
            cp[i] = (sum += cp[i]) - cp[i];
        for (i = 0; i < size; i++)
            dst[cp[((src[i] + (unsigned int)INT_MIN) >> n) & 255]++] = src[i];
        aa = src;
        src = dst;
        dst = aa;
    }
    if (src == tmp) {
        memcpy(a, src, size * sizeof(*a));
    }
    free(tmp);
}