我想知道典型的快速排序算法（即快速排序）在使用"非自然"输入而不是更标准的输入时是否保持其优势。
也就是说，如果我们有一个 0 到 N^4 范围内的 N 个整数数组，考虑到整数的范围非常宽，快速排序仍然是最快的吗？
快速排序不受数字范围的影响，而是受顺序的影响（即，如果数字已经排序或以相反的顺序排序，并且如果您选择第一个元素作为枢轴）。如果您使用随机透视方法，即使这个问题也可以解决。
总之，每种算法都有最坏情况的复杂性，通常在有关该算法的文献中讨论。
N^4 不是很大，一个包含 20 亿个整数的数组只需要每个整数 128 位即可满足该要求。 由于这至少需要 8GB 的内存存储，因此通常仅限于可以就地排序的 O（N*log（N）） 排序算法，例如快速排序，而不是需要两倍内存的 O（N） 算法。
允许 O（N） 的算法（在最好的情况下，这里不太可能）通常会受到内存的限制。 给出的示例基数排序在大数据元素中变为 O（N log（N）），因为数据实际上是可变长度的 - 考虑一个 32，768 字节的整数 - 在 64 位机器上，您的第一个存储桶可能基于前 8 个字节，第二个存储桶基于后 8 个字节，但由于非常大的范围和存储桶内的非随机分布， 大多数存储桶都很小，留下一些非常大的存储桶需要使用 O（N log（N）） 算法进行排序。 此外，此算法需要分配"存储桶"来保存每个基数的元素，这将使总内存需求翻倍。
对于需要非常昂贵比较的小元素列表，基数排序可能是一个不错的选择，但对于小列表，O（N） 和 O（N log（N）） 之间的差异可能不那么重要。
此外，对于非常昂贵的比较，例如非常大的字符串，施瓦茨变换的某些变体可能会有所帮助，并且由于每种算法都在内存和 CPU 之间平衡，因此最佳排序算法将基于使用更多内存或使用更多 CPU 之间的选择。
极端情况可能倾向于不同的排序算法，例如近似排序的列表，但通常检测这些算法的成本会很高，并且假设极端情况为真可能会导致大问题，如果
有可能它不会。说了这么多，除非绝对必要，否则所有实际实现都应该尝试将 std：：sort 与相应的 std：：hash 实现一起使用<>因为 std：：sort 可以从多个算法中进行选择，具体取决于输入数据。
所有众所周知的搜索算法都基于元素比较，即它们检查一个元素是否小于、等于或大于另一个元素。因此，它们绝对独立于范围。
但是，在某些特殊情况下，某些算法的相对性能可能与平均情况有很大差异。此类案例的示例包括：
- 除单个元素或小子集外，元素已排序。
- 元素的顺序相反。
- 除一个元素外，所有元素都是相等的。
这就是为什么对于每种排序算法，都可以确定平均和最坏情况的性能。
其他答案基本上是正确的，因为通常排序算法不会根据输入的范围而更好或更差。但是，根据输入范围，算法可能更好或更差至少有一个原因，那就是它们如何处理重复值。
例如，当重复值较多时，快速排序平均更差（有关原因的说明，请参阅此问题），当输入范围较大时，重复的可能性降低（假设它们分布在整个范围内）。