我试图通过使用冒泡排序算法按升序对数字进行排序。然而，我仍然得到一个OufOfMemory错误。
我怎么能确保我不能得到一个OufOfMemory错误在我的代码?
问题就像下面的句子。
-
内存容量限制为8MB
-
限制时间为5秒。
-
第一行给出号码个数N(1≤N≤10,000,000)。
-
从第二行开始，以N行为单位给出数字。此数为小于等于10,000的自然数。
https://www.acmicpc.net/problem/10989
这是我尝试打印数字的代码。
#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("%dn", 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("%ldn", arr[i]);
}
return 0;
}
当我猜测内存不足的原因时，似乎内存超出是由动态分配中的N * sizeof(int)引起的。如果N的取值范围是1000000，最坏的情况是N * int = 2.097.152。结果超出内存。
同样，我计算了8 MB的内存，就像下面的句子。
8 * 1024 * 1024/4 = 2.097.152
下面是期望的结果:
- 满足5秒的时间约束
- 满足8MB的内存限制
这与我的问题有关，但它不能解决我的问题。
感谢您阅读我的文章。
int可能大于存储0 ~ 10,000中的数字所需的值。这实际上是有可能的。你可以用int16_t或者uint16_t。但是一个这样的数组仍然会占用20mb或超过19mb的空间。这意味着你不可能一次把所有的数字都放到内存中。
这排除了冒泡排序。事实上，这排除了所有传统的排序(因为您可能也不能使用外部存储)。
但是由于我们排序的是小数，我们可以使用非常规的排序方法，比如计数排序。我们需要一个包含10,001个uint32_t对象的数组，也就是说刚刚超过40 KB或低于40 KiB。这远远低于你们的限额。
在时间方面，冒泡排序效率极低，可能不够快，无法达到您的目标。
使用计数排序不会有任何时间问题。