理解代码的中位数

Question

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

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

我将非常感谢对此的任何帮助。

Answer 1

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