无法将 int 类型分配给 int* 类型

Question

我正在尝试为一个函数编写代码，该函数获取一个数组(我们称之为 arr1)，其值在 32 到 64 之间，以及数组的大小(假设大小为 n)。该函数将以 O(n) 的时间对数组进行排序。

我想到的方法是声明第二个大小为 32 的数组(我们称之为 arr2)，然后执行以下操作: 对于 0 到 n 之间的每个索引 i，我们将 1 放入 arr2 中的 [arr1[i]-32] 位置。例如，如果对于当前 i，arr1[i]=40，那么我们将 1 放入 arr2 中的位置 40-32, 8。 然后我们迭代arr2，如果arr2[i]==1，那么在arr[j]中我放入i+32，j++。理论上，arr1 现在应该已排序。

我的问题是代码，当给 arr2 赋值时，我在“=”下​​面出现了一条小红线，当我将鼠标悬停在它上面时，它显示“int 类型的值不能分配给 int* 类型”

void sort_array(int* arr1,int n)
{
    int i=0,j=0;
    int* arr2[32];
    for(i=0;i<32;i++)
        arr2[i]=0;
    for(i=0;i<n;i++)
        arr2[arr1[i]-32]=1;
    for(i=0;i<32;i++)
        if(arr2[i]==1)
        {
            arr1[j]=i+32;
            j++;
        }
}

我还想听听是否有人对如何在 O(n) 内对这个数组进行排序有更好的建议。快速排序和归并排序都是nlog(n) 谢谢。

Answer 1

问题是这样的:

int* arr2[32];

这行应该是

int arr2[32];

因为arr2包含计数器，而不是指针。这就是为什么分配 1到 arr2 的元素失败。

现在让我们讨论您的算法:您尝试实现 counting sort对于具有重复值的数组将中断，因为您设置了 arr2[arr1[i]-32]至1无论您找到某件元素多少次。您应该将其更改为 arr2[arr1[i]-32]++ ，并使用计数将那么多计数值放入结果数组中。请参阅维基百科文章中的伪代码，了解正确的实现。

这里是a table comparing performances of various sorting algorithms 。查找第二个表，其中包含有关非比较排序的详细信息。