我正在努力更好地理解归约，目前我正在研究两种算法，"中值"和Quicksort。
我知道这两种算法都使用类似（实际上完全相同）的分区子程序来帮助解决它们的问题，这最终使它们非常相似。
Select(A[1...n],k): // Pseudocode for median of medians
m = [n/5]
for i from 1 to m:
B[i] = Select(A[5i-4..5i],3)
mom = Select(B[1..m],m/2)
r = partition(A[1..n],mom) // THIS IS THE SUBROUTINE
if k < r:
return Select(A[1..r-1],k)
else if k > r:
return Select(A[r+1..n],k-r)
else
return mom
那么，"归约"一词对这两种算法有意义吗？以下任何一项有意义吗？
Medians/Quicksort的中值可以简化为分区子程序
中值减少为快速排序
Quicksort降低到中位数
这实际上取决于您对"减少"的定义
通常讨论的标准类型的归约是映射归约（也称为多归约）。从问题X到问题Y的映射简化如下：
给定问题X的输入IX，将其转换为问题Y的输入IY。然后，在IY
在映射约简中，您只需要对解决问题Y的子例程进行一次调用，并且必须输出从该子例程返回的任何答案。例如，您可以将"这个数字是偶数吗？"的问题简化为"这个数字是否奇数？"，方法是在数字上加一，并输出所得数字是否为奇数。
作为映射约简的一个非示例，请考虑以下两个问题：第一，问题"这个列表中的每个布尔值都是真的吗？"，第二，问题"该列表中的一些布尔值是假的吗？？"如果你有第二个问题的解算器，您可以使用它来解决第一个问题，方法是运行第二个问题的求解器并输出相反的结果：布尔值列表中有一些元素是false，当且仅当它是而不是时，列表中的每个元素都是true。然而，这种减少不是映射减少，因为我们正在翻转子程序产生的结果。
一种常用的不同类型的归约是图灵归约。从问题X到问题Y的图灵约简如下：
建立一个解决问题X的算法，假设有一个神奇的黑匣子总是能解决问题Y。
所有映射约简都是图灵约简，但不是相反。从"一切都是真的吗？"到"是假的吗？"的上述约简不是映射约简，而是图灵约简，因为你可以使用"是假的么？"的子程序来了解列表是否包含任何假值，然后可以输出相反的值。
映射约简和图灵约简之间的另一个主要区别是，在图灵约简中，可以对解决问题Y的子例程进行多次调用，而不仅仅是一次。
您可以将快速排序和中值都看作是使用分区作为子例程的算法。在quicksort中，该子例程完成了对所有内容进行排序所需的所有繁重工作，而在中值中，它完成了缩小输入的重要步骤之一。由于这两种算法都会多次调用子例程，因此可以将其视为图灵式的约简。快速排序是从排序到分区的一种简化，而中值是从选择到分区的简化。
希望这能有所帮助！
我不认为任何一种都可以被简化为另一种（无论如何，以任何有意义的方式）。您可以使用中位数来选择快速排序的枢轴（但实际上几乎没有人这样做）。不过，Quicksort仍然需要基于pivot元素执行一些其他步骤（特别是基于pivote对数据进行分区）。
同样，中位数不能简化为Quicksort，因为Quicksort做了额外的工作，（除其他外）阻止了它满足中位数的复杂性保证。