gpt4 book ai didi

根据伪代码实现的 C 中的计数排序但无法正常运行

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:42:12 25 4
gpt4 key购买 nike

我已经根据它的伪代码(即 written on the blackboard in this video explanation)实现了计数排序,但是由于一些神秘的原因,它似乎没有正确排序。

对于测试输入:10 9 8 7 6 5 4 3 2 1

它给出:3 4 5 6 7 8 1 0 0 9

这似乎是一个非常简单的问题,但我不明白为什么会这样。

void counting(int * array, int n){

int *copy, *out, i,j, max, counter;

copy = (int*) malloc(sizeof(int) * max);

out = (int*) malloc(sizeof(int) * n );

max = array[0];

// finds max size
for(i=0;i<n;++i) if(array[i] > max) max = array[i];

// zeroes the counting array
for(i=0;i<max;++i) copy[i] = 0;

//counts
for(i=0;i<n;++i) ++copy[array[i]];

//cumulative sum
for(i=1;i<max;++i) copy[i] += copy[i-1];

//sorts
for(i=n-1;i>=1;--i){
out[copy[array[i]]] = array[i];
--copy[array[i]];
}

//overwrite original array with sorted output
for(i=0;i<n;++i) array[i] = out[i];

}

最佳答案

问题是你分配计数器数组的顺序:当你写的时候

copy = (int*) malloc(sizeof(int) * max);

max 未设置,因此其值未定义。因此,分配会产生未定义的行为,使您的程序无效。

您需要将分配移动到计算 max 的循环之后。分配 max+1 项,因为数组索引是从零开始的:

int max = array[0];
for(i=0;i<n;++i)
if(array[i] > max)
max = array[i];
copy = malloc(sizeof(int) * (max+1));

您还需要在最后free copyout 以避免内存泄漏:

free(copy);
free(out);

关于根据伪代码实现的 C 中的计数排序但无法正常运行,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46140248/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com