中位数的中位数如何与快速选择一起使用
how does median of medians work with quickselect
据我了解，medians of medians 算法递归调用 quickselect。我无法理解的是中位数的中位数应该 return。这个想法是 return 是一个很好的主元值，但是要执行快速选择，我们需要一个主元索引而不是一个主元值。我的理解有差距吗？我看了网上的资源，还是不懂。
你的理解有问题。
Quickselect（和快速排序）需要一个主元值，而不是一个主元索引。分区函数 returns 一个主元索引，这是主元值在分区后结束的位置。无法预测它会在哪里。
更准确地说，算法要求枢轴值有一个索引，因为枢轴必须是数组的一个元素，这个点在描述中可能没有被充分强调的算法。主元不属于任何一个分区（尽管具有相同值的其他元素可能是，除非您使用 three-way 分区）。这很重要，因为它保证算法最终会终止，因为两个分区都必须严格小于原始数组。如果pivot值不在数组中，有可能一个分区为空，另一个分区为原数组，可能死循环
所以枢轴必须有一个索引，但哪个索引并不重要。通常，分区算法首先将主元值交换到数组的开头（或结尾）。随着分区的进行，一些分区算法会自然地将枢轴移动到正确的点；其他算法在已知时将枢轴交换到正确的点。但其中 none 实际上受到了开始位置的影响。
Median-of-medians找到一个保证离中间不太远的pivot值，足以保证线性时间复杂度（对于quickselect）。尽管如此，它实际上只是理论上的兴趣。随机选择枢轴要快得多（代码也少得多），这足以弥补偶尔错误的枢轴选择。
据我了解，medians of medians 算法递归调用 quickselect。我无法理解的是中位数的中位数应该 return。这个想法是 return 是一个很好的主元值，但是要执行快速选择，我们需要一个主元索引而不是一个主元值。我的理解有差距吗？我看了网上的资源，还是不懂。
你的理解有问题。
Quickselect（和快速排序）需要一个主元值，而不是一个主元索引。分区函数 returns 一个主元索引，这是主元值在分区后结束的位置。无法预测它会在哪里。
更准确地说，算法要求枢轴值有一个索引，因为枢轴必须是数组的一个元素，这个点在描述中可能没有被充分强调的算法。主元不属于任何一个分区（尽管具有相同值的其他元素可能是，除非您使用 three-way 分区）。这很重要，因为它保证算法最终会终止，因为两个分区都必须严格小于原始数组。如果pivot值不在数组中，有可能一个分区为空，另一个分区为原数组，可能死循环
所以枢轴必须有一个索引，但哪个索引并不重要。通常，分区算法首先将主元值交换到数组的开头（或结尾）。随着分区的进行，一些分区算法会自然地将枢轴移动到正确的点；其他算法在已知时将枢轴交换到正确的点。但其中 none 实际上受到了开始位置的影响。
Median-of-medians找到一个保证离中间不太远的pivot值，足以保证线性时间复杂度（对于quickselect）。尽管如此，它实际上只是理论上的兴趣。随机选择枢轴要快得多（代码也少得多），这足以弥补偶尔错误的枢轴选择。