托尼·霍尔(C. A. R. Hoare)在1962年发表的关于快速排序算法的原始论文《Quicksort》.zip
托尼·霍尔(C. A. R. Hoare)在1962年发表的关于快速排序算法的原始论文,题为 "Quicksort",发表在《The Computer Journal》第5卷第1期上。这篇论文是计算机科学领域的经典文献之一,首次详细介绍了快速排序算法的原理和实现方法。 在这篇论文中,霍尔描述了一种新的排序方法,该方法适用于计算机的随机访问存储器。他比较了这种方法与其他已知的排序方法,并指出快速排序在速度、存储经济性和编程简易性方面具有显著优势。论文的第二部分还描述了一些可能有助于优化内部循环的方法的改进。 这篇论文对快速排序算法的描述是基于分治法的原则,通过将一个复杂的排序问题分解为两个更简单的子问题来解决。通过选定一个基准值(pivot),将数据分为两部分,一部分包含所有小于基准值的元素,另一部分包含所有大于基准值的元素。然后,对这两个子数组递归地应用相同的排序过程,直到所有子数组都变得足够小,可以直接排序。 霍尔的这篇论文对计算机科学领域产生了深远的影响,快速排序算法因其高效的性能和相对简单的实现而成为了最广泛使用的排序算法之一。这篇论文的发表标志着快速排序算法的正式诞生。