我正在尝试使用冒泡排序算法对数字进行升序排序。但是,我仍然收到 OufOfMemory 错误。
如何确保我的代码中不会出现 OufOfMemory 错误?
问题就像下面的句子。
8MB内存容量有限制
有5秒的时间限制。
第一行给出数字的个数N(1≤N≤10,000,000)
从第二行开始在 N 行中给出数字。这个数是小于等于10000的自然数。
这是我尝试打印数字的代码。
#include <stdio.h>
#include <stdlib.h>
void swap(int* x, int* y){
int tmp = *x;
*x = *y;
*y = tmp;
}
int main(){
int N, i, j;
scanf("%d", &N);
int* arr;
arr = (int*)malloc(N * sizeof(int));
for(i=0;i<N;i++){
scanf("%d", &arr[i]);
}
int min_value = arr[0];
for(i=0;i<N;i++){
for(j=0;j<N-i-1;j++){
if(arr[j] > arr[j+1]) {
swap(&arr[j], &arr[j+1]);
}
}
}
for(i=0;i<N;i++){
printf("%d\n", arr[i]);
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
void swap(int* x, int* y){
int tmp = *x;
*x = *y;
*y = tmp;
}
int main(){
int N;
int i, j;
scanf("%d", &N);
long* arr;
arr = (long*)malloc(N * sizeof(int));
for(i=0;i<N;i++){
scanf("%ld", &arr[i]);
}
for(i=0;i<N;i++){
for(j=0;j<N-i-1;j++){
if(arr[j] > arr[j+1]) {
swap(&arr[j], &arr[j+1]);
}
}
}
for(i=0;i<N;i++){
printf("%ld\n", arr[i]);
}
return 0;
}
当我猜测内存不足的原因时,似乎内存超出是由动态分配中的 N * sizeof(int) 引起的。如果 N 的取值范围最大为 10,000,000,最坏的情况是 N * int 为 2.097.152。结果超出了记忆。
另外,我像下面这句话一样计算了8MB的内存。
8 * 1024 * 1024 / 4 = 2.097.152
这是想要的结果:
这个和我的问题有关,但是没有解决我的问题
感谢您阅读我的帖子。
int
可能比存储 0..10,000 中的数字所需的更大。这其实很有可能。您可以使用 int16_t
或 uint16_t
。但是这些数组仍然会占用 20 MB 或超过 19 MiB。这意味着您不可能一次将所有数字放入内存中。
这排除了冒泡排序。事实上,这排除了所有常规类型(因为您可能也不能使用外部存储)。
但是由于我们要对小数进行排序,我们可以使用非常规的排序方法,例如 计数排序。我们需要一个包含 10,001 个
uint32_t
对象的数组,也就是说刚好超过 40 KB 或不到 40 KiB。这远低于您的限制。
在时间方面,冒泡排序效率极低,对于您的目标来说可能不够快。
计数排序不会有任何时间问题。