在第五章中，你看到了一个简单的排序方法，称为
冒泡排序。当时提到有
收视率显着提高。在这里，您将开发最好的版本之一：快速排序（Quicksort）。
快速分类，由C.A.R.发明并命名Hoare，是目前最好的通用分类算法。我无法在第五章中展示它，因为快速排序的最佳实现是基于递归的。我们将开发的版本对字符数组进行排序，但逻辑可以适应对任何类型的对象进行排序。
快速排序是基于分区的思想。一般过程包括选择一个值（称为比较），然后将数组分为两部分。所有大于或等于分区值的元素都插入到一侧，较小的元素插入到另一侧。对每个剩余部分重复此过程，直到数组排序完毕。例如，给定数组 fedacb 并使用值 d 作为比较，快速排序的第一遍将重新排列数组，如下所示：

初始 f e d a c b
第 1 段 b c a d e f

然后对每个部分（即 bca 和 def）重复此过程。正如您所看到的，该过程本质上是递归的，事实上，快速排序的最干净的实现是递归的。
您可以通过两种方式选择比较值。您可以随机选择它，也可以通过查找从数组中获取的一小组值的平均值来选择它。为了获得最佳分类，您必须选择正好位于值范围中间的值。然而，对于大多数数据集来说，做到这一点并不容易。最坏的情况是所选值位于一端。即便如此，快速排序仍能正确运行。
我们将开发的快速排序版本选择数组的中间元素作为比较。

参见QSDemo.java。

快速排序：

• 最高效、使用最广泛的分类算法之一。
• 由 C.A.R. 发明霍尔。
• 基于分区的概念，其中数组被分为递归排序的部分。
• 比冒泡排序等简单方法更高效。

手术：

• 比较值（枢轴）：
• 选择一个值作为参考（枢轴），并围绕该值组织数组。
• 小于主元的元素移至一侧，较大的元素移至另一侧。
• 对每个部分递归地重复该过程，直到数组完全排序。

快速排序

QS演示