c++ - 中位数的中位数理解代码

Question

我在这里找到了 c++ 中的算法实现 https://gist.github.com/andlima/1774060 但我不明白几行的目的以及它们是如何工作的，

1. 我是否应该添加一个 if 语句，如果 n 低于一定数量，我们应该对数组进行排序并返回 v[k]？
2. 在第 4 行中，为什么我们通过将变量增加 4 来创建变量？我知道我们必须将它除以 5 才能拥有一定数量的小数组
3. 6行中的“for循环”负责什么？是否将主数组拆分为我们想要排序的较小数组，然后创建一个中位数数组？为什么有一个交换函数，为什么我们把它分成 if 和 else 条件？
4. 为什么我们在之前调用相同的函数行后删除中位数数组
5. 第 25 行中的 for 循环和第 33 行中的循环以及第 38 行中的交换的目的是什么？

对于这方面的任何帮助，我将不胜感激。

Answer 1

1. 这是一个优化。一个实现可以做到这一点，但它不必这样做。
2. 加四是为了将除法的结果四舍五入。这是整数除法的常见技巧：如果您想将除以的结果四舍五入，请在除法之前N添加N-1。
3. 第 6 行的循环负责迭代数组的五个元素块。if条件检查块是否有五个元素。里面的for循环执行选择排序，交换元素以将中值放在索引处w[2]
4. 一旦递归调用结束，我们就删除medians，因为算法的其余部分不需要它。
5. 第 25 行的循环移动pivot到数组的结束位置。