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

Question

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

我想这样做的方法是声明第二个数组(我们称之为 arr2)，大小为 32，然后执行以下操作:对于 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 .查找第二个表，其中包含有关非比较排序的详细信息。