它是如何工作的？

快速排序分为三个步骤：选择基准、分区和递归。

分步过程：

1. 选择基准：选择一个元素作为基准。在本课程中，我们始终使用最后一个元素。
2. 分区：遍历其他元素，将它们分成小于基准的元素和大于或等于基准的元素。
3. 递归：用相同的方法对较小的一组和较大的一组进行排序，然后将它们重新组合为已排序的较小组 + 基准 + 已排序的较大组。

以 [7, 2, 9, 4] 为例：

• 基准是 4（最后一个元素）。对其余元素 [7, 2, 9] 进行分区：小于 4 的元素是 [2]，其余元素是 [7, 9]。
• 对 [2] 排序（已经有序），并对 [7, 9] 排序（基准为 9，得到 [7, 9]）。
• 合并：[2] + [4] + [7, 9] = [2, 4, 7, 9]。