如果我使用散列对数组进行排序，在性能方面会有什么样的缺点？

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]);
    }
}

该算法运行时间复杂度为 O(max_element)。仅考虑性能（时间和 space），我在这里面临什么样的缺点？

Answer 1

您可能考虑的问题：

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

Answer 2

您实现的算法称为 counting sort。它的运行时间是 O(n + U)，其中 n 是元素的总数，U 是数组中的最大值（假设数字从 0 到 U），它的 space 用法是 Θ(U ).您的特定实施假定 U = 10,000。尽管您将您的方法描述为 "hashing," 这实际上不是散列（计算元素的某些功能并使用它来将它们放入桶中）作为 distribution（根据元素的值分布元素）。

如果 U 是一个固定常量——就像你的情况一样——那么运行时间是 O(n) 并且 space 用法是 O(1)，但请记住 big-O 谈论长-term 增长率，如果 U 很大，运行时间可能会非常高。如果您要对具有有限范围值的非常大的数组进行排序，这将使其具有吸引力。但是，如果值的范围可以很大，这不是一个特别好的方法。有趣的是，您可以将基数排序视为一种重复运行计数排序的算法，其中 U = 10（如果使用数字的 10 进制数字）或 U = 2（如果使用二进制）并且运行时间为 O(n log U)，这对于大的 U 值是非常可取的。

您可以通过多种方式清理此代码。例如，您有一个 if 语句和一个具有相同条件的 while 循环，它们可以组合在一起成为一个 while 循环。您可能还想进行一些断言检查，以确保所有值都在 0 到 9,999 的范围内（含 0 到 9,999），否则会出现边界错误。此外，您可以考虑将全局数组设为局部变量（尽管注意您的堆栈使用情况）或 static 局部变量（以避免污染全局名称 space）。您也可以让用户传入指定最大大小的参数，或者可以自己计算。

如果我使用散列对数组进行排序，在性能方面会有什么样的缺点？

What kind of drawbacks are there performance-wise , if I sort an array by using hashing?

arrays

sorting

time-complexity

space-complexity

counting-sort