为什么快速排序被称为“快速排序”？

Question

这个问题的要点不是讨论这个算法的优点，而不是任何其他排序算法--当然还有许多其他的问题。这个问题是关于名字的。为什么快速排序被称为“快速排序”？当然，大部分时间都是“快”的，但并不总是如此。退化为O(N^2)的可能性是众所周知的。对于快速排序有各种各样的修改可以缓解这个问题，但是那些将最坏的情况降到保证的O(n log )的修改通常不再被称为快速排序。(例如Introsort)。

我只是想知道为什么在所有著名的排序算法中，这是唯一一个值得命名为“快速”的算法，它描述的不是算法是如何工作的，而是它的速度(通常)。Mergesort之所以被称为Mergesort，是因为它合并了数据。之所以调用Heapsort，是因为它使用堆。Introsort从“内省”中获得它的名称，因为它监视自己的性能，以决定何时从快速排序切换到Heapsort。同样，对于所有速度较慢的程序-- Bubblesort、插入排序、选择排序等等--它们都是以它们的工作方式命名的。我能想到的唯一的例外是“博戈斯特”，这实际上只是一个没有人在实践中真正使用的玩笑。为什么快速排序不被称为描述性更强的东西，比如“分区排序”或“数据透视排序”，它们描述了它实际上所做的事情？这甚至不是“先到这里”的案子。Mergesort是在快速排序之前15年开发的。(1945年和1960年分别根据维基百科)

我想这更像是一个历史问题，而不是编程问题。我只是好奇它是怎么得名的--这只是一个很好的营销吗？

Answer 1

1962年，对排序算法的研究没有今天那么深入，计算机科学家托尼·胡雷发现了一种比其他算法更快的新算法，因此他发表了一篇名为快速排序的纸张，并引用了这篇论文的标题。

引用摘要：

描述了计算机随机存取存储器中的一种新的排序方法.与其他已知方法相比，该方法在速度、存储经济和编程方便等方面都有很好的优势。本文的第二部分介绍了该方法的一些改进，这些改进对于优化内环是有帮助的。

Answer 2

我相信这个名字最初是以发明家的名字命名的，但由于Hoare听起来有点接近妓女的英语，所以这个名字很早就被更改了。至于为什么他们选择“快速”而不是其他的东西，我不确定。

Answer 3

我相信这是因为，当它被发明的时候，它比所有算法都快(或者说，大多数，因为速度也在很大程度上取决于数据类型，在某些情况下，其他算法变得比快速排序快得多)。

所以是的，这是历史的(但是我不太清楚这段历史.)

但我同意它的名字应该包含算法的提示.