为什么我们不能使用复杂度为 O(1) 的快速排序，即使我们有一个包含 1 项的列表？
Why can't we have a Quick Sort with a complexity of O(1), even if we have a list of 1 item?
虽然这样做真的很愚蠢，但我觉得只要有正确的算法，它绝对可以做到。也就是说，为什么快速排序的最佳情况不是 O(1)？
虽然您可以通过检查输入的大小和这种情况下的短路来开始您的实施，但我对快速排序的描述仍然会执行许多步骤。
我读到的第一步是计算一个索引，该索引将子数组划分为两个分区，其中一个或两个分区都可以为空。然后使用快速排序递归地对这些子数组进行排序（假设它们是空的，这就是你结束递归的地方）。子数组现在已排序。据说是最坏情况 Θ(n2) 和平均情况 O(n lg n) .如果你用 1 代替 n 是的，它看起来有点恒定，但 O 是一个界限，不以这种方式使用。
就是说，我看到的实现只会在子数组的低索引输入小于高索引输入时才进行分区。即子数组中至少有 2 个元素。
必须为 size-1 甚至 size-0 列表定义 QuickSort 的任何实现，因为当您递归地将集合分成更小的部分时，您将不可避免地 运行 分成这些大小的子集。 运行 写在纸上，你就会看到。
why wouldn't the best case scenario for a quick sort be O(1)?
这是对大O表示法的误解。它描述了算法如何根据元素数量进行缩放。 QuickSort 永远不会是 O(1)，因为它至少必须 运行 通过其递归除法策略一次，这需要 (N*(log N)) 次迭代（因此在 O(N*(log N)) 中缩放最好的情况）。
虽然这样做真的很愚蠢，但我觉得只要有正确的算法，它绝对可以做到。也就是说，为什么快速排序的最佳情况不是 O(1)？
虽然您可以通过检查输入的大小和这种情况下的短路来开始您的实施，但我对快速排序的描述仍然会执行许多步骤。
我读到的第一步是计算一个索引，该索引将子数组划分为两个分区，其中一个或两个分区都可以为空。然后使用快速排序递归地对这些子数组进行排序（假设它们是空的，这就是你结束递归的地方）。子数组现在已排序。据说是最坏情况 Θ(n2) 和平均情况 O(n lg n) .如果你用 1 代替 n 是的，它看起来有点恒定，但 O 是一个界限，不以这种方式使用。
就是说，我看到的实现只会在子数组的低索引输入小于高索引输入时才进行分区。即子数组中至少有 2 个元素。
必须为 size-1 甚至 size-0 列表定义 QuickSort 的任何实现，因为当您递归地将集合分成更小的部分时，您将不可避免地 运行 分成这些大小的子集。 运行 写在纸上，你就会看到。
why wouldn't the best case scenario for a quick sort be O(1)?
这是对大O表示法的误解。它描述了算法如何根据元素数量进行缩放。 QuickSort 永远不会是 O(1)，因为它至少必须 运行 通过其递归除法策略一次，这需要 (N*(log N)) 次迭代（因此在 O(N*(log N)) 中缩放最好的情况）。