给定一个大数字时程序崩溃

Question

我正在尝试用 C 编写 merge sort algorithm。问题是它不适用于大量元素。如果数组有 100000 个元素，那没问题，但如果它有 1e6 或 1e7，它就会崩溃。我认为你不能为数组提供如此多的元素，但在我读到这不是真的之后，你应该能够提供 1e7 个元素。之后我想也许 int 范围太小了，但事实并非如此，int 到 1e9。我真的不知道是什么问题以及为什么它不起作用，所以请帮忙。提前致谢！

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

int n;
void merge(int *, int, int);
void mergeSort(int *, int, int);
void bubbleSort(int *, int);

int main() {
//    scanf("%d",&n);
    n = 10000000;
    int *a = (int *)malloc(n * sizeof(int));
    if (a == NULL) {
        printf("Nu s-a putut aloca memorie.");
        exit(0);
    }
    for (int i = 0; i < n; i++)
        a[i] = rand() % 50;

    mergeSort(a, 0, n - 1);
    //bubbleSort(a, n - 1);

//  for (int i = 0; i < n; i++) {
//      printf("%d ", a[i]);
//  }
    free(a);
    return 0;
}

void merge(int *a, int start, int sfarsit) {
    int mij = (start + sfarsit) / 2;
    int i = start;
    int j = mij + 1;
    int k = start;
    int aux[10000000];

    while (i <= mij && j <= sfarsit) {
        if (a[i] < a[j])
            aux[k++] = a[i++];
        else
            aux[k++] = a[j++];
    }
    while (i <= mij)
        aux[k++] = a[i++];
    while (j <= sfarsit)
        aux[k++] = a[j++];
    for (int i = start; i <= sfarsit; i++)
        a[i] = aux[i];
}

void mergeSort(int *a, int start, int sfarsit) {
    if (start >= sfarsit)
        return ;

    int mij = (start + sfarsit) / 2;

    mergeSort(a, start, mij);
    mergeSort(a, mij + 1, sfarsit);
    merge(a, start, sfarsit);
}

Answer 1

这个：

int aux[10000000];

有问题。这对堆栈来说太过分了。更改为：

int *aux = malloc(sizeof(*aux) * 10000000);

当然需要在函数merge的最后使用free(aux)，还要检查是否分配成功。

此外，您当然应该根据 sfarsit 进行分配，但从您的其他代码来看，我似乎不需要告诉您。

Answer 2

你的程序有这个问题：merge 函数中的定义 int aux[10000000]; 定义了一个具有自动存储功能的临时数组（又名 在堆栈上 ），它是：

非常大，可能对您的系统来说太大，导致堆栈溢出。
如果要排序的数组大于 1000 万个元素，则不需要足够大。

您应该分配这个临时数组，可以在 merge 本地分配，也可以在使用额外参数调用 mergesort 的包装函数中分配。

将n设为全局变量也是不必要的，而且很容易出错。

这是修改后的版本：

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

int mergeSort(int *a, int length);
void bubbleSort(int *, int);

int main() {
    int n;
    int *a;

    n = 10000000;
    //scanf("%d", &n);
    if ((a = malloc(sizeof(*a) * n)) == NULL) {
        printf("Nu s-a putut aloca memorie.");
        return 1;
    }
    for (int i = 0; i < n; i++)
        a[i] = rand() % 50;

    mergeSort(a, n);
    //bubbleSort(a, n);

    for (int i = 1; i < n; i++) {
        if (a[i] < a[i - 1]) {
            printf("mergeSort failed\n");
            break;
        }
    }
    free(a);
    return 0;
}

void merge(int *a, int start, int mij, int sfarsit, int *aux) {
    int i = start;
    int j = mij + 1;
    int k = start;

    while (i <= mij && j <= sfarsit) {
        if (a[i] <= a[j])
            aux[k++] = a[i++];
        else
            aux[k++] = a[j++];
    }
    while (i <= mij)
        aux[k++] = a[i++];

    while (j <= sfarsit)
        aux[k++] = a[j++];

    for (i = start; i <= sfarsit; i++)
        a[i] = aux[i];
}

void mergeSortAux(int *a, int start, int sfarsit, int *aux) {
    if (start >= sfarsit)
        return;

    int mij = (start + sfarsit) / 2;

    mergeSortAux(a, start, mij, aux);
    mergeSortAux(a, mij + 1, sfarsit, aux);
    merge(a, start, mij, sfarsit, aux);
}

int mergeSort(int *a, int length) {
    if (length > 1) {
        int *aux = malloc(sizeof(*aux) * length);
        if (aux == NULL)
            return -1;
        mergeSortAux(a, 0, length - 1, aux);
        free(aux);
    }
    return 0;
}

请注意，您可以改进此代码：

对数组大小和索引变量使用 size_t 而不是 int
使用包含 start 和排除 stop 的约定，这避免了 +1/-1 调整。
不复制右侧切片中的剩余值，因为它们已经存在于原始数组中。

这是修改后的版本：

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

int mergeSort(int *a, size_t length);

int main(int argc, char *argv[]) {
    size_t n = 10000000;
    int *a;
    int res = 0;

    if (argc > 1) {
        n = strtoll(argv[1], NULL, 0);
    }
    if ((a = malloc(sizeof(*a) * n)) == NULL) {
        printf("Nu s-a putut aloca memorie.");
        return 1;
    }
    for (size_t i = 0; i < n; i++) {
        a[i] = rand() % 50;
    }
    if (mergeSort(a, n)) {
        printf("mergeSort failed: allocation error\n");
        res = 1;
    } else {
        for (size_t i = 1; i < n; i++) {
            if (a[i] < a[i - 1]) {
                printf("mergeSort failed: out of order\n");
                res = 1;
                break;
            }
        }
    }
    free(a);
    return res;
}

void merge(int *a, size_t start, size_t mid, size_t stop, int *aux) {
    size_t i = start;
    size_t j = mid;
    size_t k = start;

    while (i < mid && j < stop) {
        if (a[i] <= a[j])
            aux[k++] = a[i++];
        else
            aux[k++] = a[j++];
    }
    while (i < mid)
        aux[k++] = a[i++];

    for (i = start; i < k; i++)
        a[i] = aux[i];
}

void mergeSortAux(int *a, size_t start, size_t stop, int *aux) {
    if (stop - start >= 2) {
        size_t mid = start + (stop - start) / 2;

        mergeSortAux(a, start, mid, aux);
        mergeSortAux(a, mid, stop, aux);
        merge(a, start, mid, stop, aux);
    }
}

int mergeSort(int *a, size_t length) {
    if (length > 1) {
        int *aux = malloc(sizeof(*aux) * length);
        if (aux == NULL)
            return -1;
        mergeSortAux(a, 0, length, aux);
        free(aux);
    }
    return 0;
}

给定一个大数字时程序崩溃

Program crashes when given a big number

c

crash

mergesort

bigdata

dynamic-memory-allocation