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 行中的 this 以及第 38 行中的 swap 的目的是什么？

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

Answer 1

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