有多种排序算法可用。时间复杂度为O(n^2)的排序算法可能适用于O(nlogn)，因为它是适当的或稳定的。例如：
- 对于有些排序的东西，插入排序是好的
- 对几乎排序的数组应用快速排序是愚蠢的
- 堆排序对于O(nlogn)是好的，但不稳定
- 合并排序不能在嵌入式系统中使用，因为在最坏的情况下，它需要O(n)的空间复杂性
我想知道哪种排序算法在什么条件下合适。
- 哪种排序算法最适合按字母顺序排序名称
- 哪种排序算法最适合对较少的整数进行排序
- 哪种排序算法最适合对较少整数进行排序，但范围可能较大(98767–6734784)
- 哪种排序算法最适合对数十亿个整数进行排序
- 在空间和时间都受到约束的嵌入式系统或实时系统中，哪种排序算法最适合排序
请建议这些/其他情况、书籍或网站进行此类比较。
好吧，没有银弹，但这里有一些经验法则：
- 当元素的范围(设为
U)与元素的数量(U<<n)相比相对较小时，基数排序/计数排序通常是好的(可能适合您的情况2，4) - 插入排序适用于较小的(比如
n<30)列表，甚至比O(nlogn)算法更快(根据经验)。事实上，当n<30时，您可以通过切换到插入排序来优化O(nlogn)自上而下的算法 - 基数排序的变体也可能是按字母顺序排序字符串的好选择，因为它是
O(|S|*n)，而基于比较的普通算法是O(|S|*nlogn)[其中|S|是字符串的长度]。(适合您的情况1) - 如果排序后的输入非常大，太大而无法放入合并中，则使用外部排序(这是一种变体或合并排序)，它可以最大限度地减少磁盘读/写的次数，并确保这些操作按顺序进行，因为它大大提高了性能。(可能适合案例4)
- 对于一般的大小写排序，快速排序和timsort(用于java)性能良好
Merge排序不能在嵌入式系统中使用，因为在最坏的情况下需要O(n)的空间复杂性。
您可能对C++中的stable_sort函数感兴趣。它试图为常规合并排序分配额外的空间，但如果失败，它会执行时间复杂度较低的就地稳定合并排序(n * ((log n)^2)而不是n * (log n))。如果你能阅读C++，你可以在你最喜欢的标准库中查看实现，否则我希望你能在语言不可知的地方找到解释的细节。
有大量关于就地稳定排序(尤其是就地合并)的学术文献。
因此，在C++中，经验法则很简单，"如果需要稳定排序，则使用std::stable_sort，否则使用std::sort"。Python让它变得更加容易，经验法则是"使用sorted"。
一般来说，你会发现很多语言都有相当聪明的内置排序算法，而且大多数时候你都可以使用它们。很少需要实现自己的库来击败标准库。如果你确实需要实现自己的算法，那么除了拿出课本，用你能找到的尽可能多的技巧实现一些算法，并针对你担心的特定情况对它们进行测试之外，没有什么可以替代的了，因为你需要击败库函数。
在回答这个问题时，您可能希望得到的大多数"显而易见"的建议都已经包含在一种或多种常见编程语言的内置排序函数中。但要回答您的具体问题：
哪种排序算法最适合按字母顺序排序名称？
基数排序可能会超过C++sort等标准比较排序，但如果对名称使用"正确"的排序规则，则这可能是不可能的。例如，"McAlister"过去的字母顺序与"MacAlister"相同，"St.John"则与"Saint John"相同。但后来程序员出现了，他们只想按ASCII值排序，而不是编写许多特殊规则，所以大多数计算机系统不再使用这些规则。我发现周五下午是这类专题的好时机；-)如果对"规范化"名称的字母而不是实际名称进行基数排序，则仍然可以使用基数排序。
英语以外的其他语言的"适当"校勘规则也很有趣。例如，在德语中，"Grüber"的排序类似于"Grueber"，因此在"Gruber"之后，但在"Gruhn"之前。在英语中，"Llewellyn"这个名字在"Lewis"之后，但我相信在威尔士语中(使用完全相同的字母表，但不同的传统排序规则)它在之前。
因此，谈论优化字符串排序比实际操作更容易。对字符串进行"正确"排序需要能够插入特定于区域设置的排序规则，如果您放弃比较排序，则可能需要重写所有排序规则。
哪种排序算法最适合排序较少的整数？
对于少量的小值，可能是计数排序，但当数据变得足够小(20-30个元素)时，切换到插入排序的Introsort非常好。Timsort在数据不是随机的情况下特别好。
哪种排序算法最适合对较少整数进行排序，但范围可能很大(98767–6734784)？
大范围排除计数排序，因此对于少量范围广泛的整数，Introsort/Timsort。
哪种排序算法最适合对数十亿个整数进行排序？
如果你所说的"数十亿"是指"太多了，无法放入内存"，那么这会稍微改变游戏。也许你想把数据分成适合记忆的块，Intro/Tim对每个块进行排序，然后进行外部合并。如果你在一台64位机器上对32位整数进行排序，你可以考虑计数排序
在空间和时间都受到约束的嵌入式系统或实时系统中，哪种排序算法最适合排序？
可能是Introsort。
对于有些排序的东西，插入排序是很好的。
True，Timsort也利用了同样的情况。
在几乎排序的数组上应用快速排序是愚蠢的。
错误。没有人使用Hoare最初发布的简单快速排序，你可以更好地选择数据透视，使杀手案例远不如"排序数据"明显。为了彻底处理坏案例，有Introsort。
堆排序对O(nlogn)很好，但不稳定。
没错，但Introsort更好(也不稳定)。
Merge排序不能在嵌入式系统中使用，因为在最坏的情况下，它需要O(n)的空间复杂性。
通过像std::stable_sort那样允许较慢的就地合并来处理此问题。