为什么我们需要这么多排序技术？

Question

数据结构中有大量的排序技术如下 -
选择排序
冒泡排序
递归冒泡排序
插入排序
递归插入排序
合并排序
迭代合并排序
快速排序
迭代快速排序
堆排序
计数排序
基数排序
桶排序
壳排序时间
排序
梳状排序
鸽子洞排序
循环排序
鸡尾酒排序
链排序
等等。
我们需要所有这些吗？

Answer 1

在早期的计算机科学课程中讨论和研究排序算法的主要原因是因为它们提供了非常好的学习材料。排序的问题很简单，是展示几种算法策略的好借口；几种数据结构；如何实施；并讨论时间复杂度和空间复杂度；即使它们显然解决了相同的问题，算法也可以具有不同的属性。

在实践中，编程语言的标准库通常包含一个默认sort函数，例如std::sort在 C++ 或list.sortPython 中；几乎在所有情况下，您都应该信任该函数及其使用的算法。

但是你学到的关于排序算法的一切都是有价值的，可以应用于其他问题。以下是可以通过研究排序算法来学习的非详尽列表：

• 分而治之；
• 堆；
• 二叉搜索树，包括不同类型的自平衡二叉搜索树；
• 选择合适的数据结构的重要性；
• 就地和非就地之间的区别；
• 稳定排序和非稳定排序的区别；
• 递归方法和迭代方法；
• 如何计算时间复杂度，如何比较两种算法的效率；

Answer 2

有这么多不同的排序算法存在，没有单一的原因。这是排序算法及其来源的采样器，以更好地了解它们的起源：

• 基数排序是在 1800 年代后期发明的，用于对美国人口普查的穿孔卡片进行物理排序。它今天仍在软件中使用，因为它在数字和字符串数据上非常快。
• 合并排序似乎是由约翰·冯·诺依曼发明的，用于验证他的存储程序计算机模型（冯·诺依曼架构）。它可以很好地作为低内存计算机处理通过机器传输的数据的排序算法，因此它在 1960 年代和 1970 年代很受欢迎。它是分而治之技术的绝佳测试平台，使其在算法课程中很受欢迎。
• 插入排序似乎一直存在。尽管在最坏的情况下它很慢，但它在小输入和主要排序的数据上非常棒，并且被用作其他快速排序算法的构建块。
• Quicksort 于 1961 年发明。它与处理器缓存配合得非常好，因此它持续流行。
• 许多年前，人们对排序网络进行了广泛的研究。它们仍然可以用作诸如签名排序之类的理论概念验证算法中的构建块。
• Timsort 是为 Python 发明的，旨在通过利用常见的分布和模式，比其他排序更快地对实际的、真实世界的序列进行排序。
• Introsort 被发明为一种实用的方法，可以利用快速排序的速度而不会出现最坏的情况。
• Shellsort 是五十多年前发明的，在当时的计算机上非常实用。对于当时研究它的人来说，探索它的理论极限是一个困难的数学问题。
• Thorup 和 Yao 的 O(n sqrt(log log n)) 时间整数排序算法旨在探索使用字级并行性的高效算法的理论极限。
• 循环排序源于群论中对排列的研究，旨在最大限度地减少对列表进行排序时进行的内存写入次数。
• Heapsort 值得注意的是就地排序，但在实践中速度很快。它基于隐式表示非平凡数据结构的想法。

这甚至不是一个详尽的排序算法列表，但希望让您了解那里有什么以及为什么。:-)