我正在尝试在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);
}
此:
int aux[10000000];
是问题。对于堆栈来说,这将是非常重要的。更改为此:
int *aux = malloc(sizeof(*aux) * 10000000);
当然,您需要在函数free(aux)
的末尾使用merge
,还要检查分配是否成功。
此外,您当然应该相对于sfarsit
进行分配,但是从您的其他代码来看,似乎我不需要告诉您。