时间和空间复杂度

时间复杂度：

• 平均情况：O(n log n)
  • 平衡的基准值每次都会将数组大致分成两半，因此会产生约 log n 层，每层的分区工作量为 O(n)。
• 最坏情况：O(n²)
  • 如果基准值始终是最小或最大的元素（例如，数组已经排好序，且选择最后一个元素作为基准值），那么每次都会有一侧为空，递归深度会达到 n 层。

空间复杂度：

• 这里实现的版本需要 O(n) 空间，因为每一步都会创建新的较小元素列表和较大元素列表。经典的原地快速排序可以将额外空间降至 O(log n)。

总结：

• 快速排序的平均速度非常快，在实际应用中是常用的排序算法。
• 选择不佳的基准值可能会使它的时间复杂度退化到 O(n²)；采用良好的基准值策略（例如随机选择或选择中位数元素）可以避免这种情况。