在第五章中，你看到了一個簡單的排序方法，稱為
冒泡排序。當時提到有
收視率顯著提高。在這裡，您將開發最好的版本之一：快速排序（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演示