pivot索引和平衡分区（Java） 7 月 Questions & Answers 139 对于快速排序的big-O pivot索引创建平衡分区意味着什么 我知道pivot index是指索引左边的数字之和等于索引右边的数字之和的索引 当它创建平衡分区和不创建平衡分区时，它会如何影响复杂性
# 1 楼答案 在快速排序中，主要思想是使用枢轴递归地划分数组 在最好的情况下，选择的枢轴总是将数组平均分成2。例如，如果有一个未排序的数组[1,3,2,6,4,7,5]，那么将数组一分为二的枢轴是4。这是因为使用这个轴对数组进行分区，可以得到[1,2,3,4,5,6,7]，轴的每一侧有3个元素 在编写这种情况下的递归关系时，您会得到：T(n) = 2 T(n/2) + O(n)，因为n大小的数组现在可以被视为2个n/2大小的数组，并且分区过程需要O（n）个时间。使用主定理/其他方法来展开递归，可以得到O（nlogn）作为快速排序的运行时 不幸的是，这样的理想情况在现实生活中并不总是可能的，因为你选择的支点可能不是一个很好的支点。但是，一般来说，如果选择一个随机轴，仍然有很大机会将阵列划分为两个大小合理的部分。特别是，如果可以实现1:9的拆分，那么可以从数学上证明快速排序的运行时仍然是O（nlogn）。这被称为随机快速排序，网上有很多资源可以解释其背后的概率分析。这里是one such resource
# 1 楼答案
在快速排序中，主要思想是使用枢轴递归地划分数组
在最好的情况下，选择的枢轴总是将数组平均分成2。例如，如果有一个未排序的数组[1,3,2,6,4,7,5]，那么将数组一分为二的枢轴是4。这是因为使用这个轴对数组进行分区，可以得到[1,2,3,4,5,6,7]，轴的每一侧有3个元素
在编写这种情况下的递归关系时，您会得到：
T(n) = 2 T(n/2) + O(n)，因为n大小的数组现在可以被视为2个n/2大小的数组，并且分区过程需要O（n）个时间。使用主定理/其他方法来展开递归，可以得到O（nlogn）作为快速排序的运行时不幸的是，这样的理想情况在现实生活中并不总是可能的，因为你选择的支点可能不是一个很好的支点。但是，一般来说，如果选择一个随机轴，仍然有很大机会将阵列划分为两个大小合理的部分。特别是，如果可以实现1:9的拆分，那么可以从数学上证明快速排序的运行时仍然是O（nlogn）。这被称为随机快速排序，网上有很多资源可以解释其背后的概率分析。这里是one such resource