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

Question

我有这段代码，但它在处理过程中崩溃了。系统给出消息“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);
}

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

Radix sort for 10^6 array in C

c

radix-sort