我正在学习C语言并尝试使用递归快速排序算法。在输入规模较小的情况下,它按预期工作;对于随机生成的数组,它在所有测试规模(最高达100,000)上都没有问题。但是,对于降序数组,在某个数组大小(32,506)处程序崩溃了(Windows给我一个消息说程序已停止工作)。我的代码中是否存在任何错误(例如错误的内存分配-我不确定是否正确),或者C语言是否有递归调用的限制,还是其他方面出现了问题?
编辑: 我知道我的快速排序实现比较简单,并且在这种类型的输入情况下表现很差,但我没有预料到它会崩溃。
我正在使用GCC和MinGW在Windows 10的命令提示符上运行。我不确定发生了什么,因为除了Windows告诉我程序已停止工作之外,我并没有得到任何具体的错误消息。
编辑: 我知道我的快速排序实现比较简单,并且在这种类型的输入情况下表现很差,但我没有预料到它会崩溃。
我正在使用GCC和MinGW在Windows 10的命令提示符上运行。我不确定发生了什么,因为除了Windows告诉我程序已停止工作之外,我并没有得到任何具体的错误消息。
#include <stdio.h>
#include <stdlib.h>
int partition(int *a, int lo, int hi) {
int i = lo; int j = hi+1; int v,t;
v = a[lo]; //partition element
while (1) {
while (a[++i] < v) {if (i == hi) break;}
while (v < a[--j]) {if (j == lo) break;}
if (i >= j) break;
t = a[j]; a[j] = a[i]; a[i]= t; //swap
}
t = a[lo]; a[lo] = a[j]; a[j]= t;//swap
return j;
}
void quicksort(int a[], int lo, int hi) {
int j;
if (hi <= lo) return;
j = partition(a, lo, hi);
quicksort(a, lo, j-1);
quicksort(a, j+1, hi);
}
int main() {
int len;
for (len = 32000;len < 40000;len+=100) {
printf("New Arr with len = %d\n",len);
int *arr;
arr = (int*) calloc(len,sizeof(int));
int j;
//create descending Array
for (j = 0; j < len; ++j) {
arr[j] = len-j;
}
printf("start sorting\n");
quicksort(arr,0,len-1);
free(arr);
}
}
calloc
可能会失败。 - William Pursell