如果我用散列对数组排序，在性能方面有什么缺点?

Question

我编写了一个简单的函数，使用散列对数组int a[];进行排序。为此，我将每个元素的频率存储在新数组hash1[]中，然后以线性时间放回到原始数组中。

#include<bits/stdc++.h>
using namespace std;
int hash1[10000];
void sah(int a[],int n)
{
    int maxo=-1;
    for(int i=0;i<n;i++)
    {
        hash1[a[i]]++;
        if(maxo<a[i]){maxo=a[i];}
    }
    int i=0,freq=0,idx=0;
    while(i<maxo+1)
    {
        freq=hash1[i];
        if(freq>0)
        {
            while(freq>0)
            {
                a[idx++]=i;freq--;
            }
        }
        i++;
    }
}
int main()
{
    int a[]={6,8,9,22,33,59,12,5,99,12,57,7};
    int n=sizeof(a)/sizeof(a[0]);
    sah(a,n);
    for(int i=0;i<n;i++)
    {
        printf("%d ",a[i]);
    }
}

该算法运行时间为0 (max_element)。如果只考虑性能(时间和空间)，我在这里面临什么样的劣势?

Answer 1

您实现的算法称为计数排序。它的运行时间为O(n + U)，其中n是元素的总数，U是数组中的最大值(假设数字从0到U)，其空间使用情况为Θ(U)。您的特定实现假设U = 10,000。尽管您已经将您的方法描述为"哈希"，但这确实不是哈希(计算元素的某些函数并使用它将它们放入桶中)作为分布(根据它们的值将元素分散)。

如果U是一个固定的常数——就像你的情况一样——那么运行时是O(n)，空间使用是O(1)，不过请记住，大O指的是长期增长率，如果U很大，运行时可能会相当高。如果对值范围有限的非常大的数组进行排序，这将使其具有吸引力。然而，如果值的范围可能很大，这不是一个特别好的方法。有趣的是，您可以将基数排序视为一种算法，它重复运行计数排序，U = 10(如果使用基数的10位数)或U = 2(如果使用二进制)，并且运行时间为O(n log U)，这对于U的大值是非常可取的。

可以用多种方法清理这段代码。例如，您有一个具有相同条件的if语句和一个while循环，它们可以组合成一个单独的while循环。您可能还需要进行一些断言检查，以确保所有值都在0到9999(包括在内)的范围内，否则就会出现边界错误。此外，可以考虑将全局数组设置为局部变量(尽管要注意堆栈使用情况)或static局部变量(以避免污染全局命名空间)。您也可以让用户传递一个参数来指定最大大小，或者可以自己计算。

Answer 2

您可以考虑的问题:

• 输入验证。如果用户输入-10或一个非常大的值该怎么办?
• 如果最大元素很大，那么当L1缓存耗尽时，您将在某些时候受到性能影响。hash1 -array将与a -array竞争内存带宽。当我过去实现基数排序时，我发现每次迭代8位是最快的。
• 时间复杂度实际上是0 (max_element + number_of_elements)。例如，如果你对200万个1或0进行排序。它不如排序2个1或0快。