这里是否值得实现一种排序算法？

Question

我有一个正整数列表，希望将其中最大的三个值存储在变量 h1、h2 和 h3 中。其余值不相关。

我考虑使用 int* 管理它们，并在填充时使用 realloc 调整内存大小，然后使用适当的排序算法进行排序，但这是否真的值得呢？由于我实际上不需要对整个数组进行排序，所以我只是这样做：

if (currentVal > h3) {
    h3 = currentVal;
    if (currentVal > h2) {
        h3 = h2;
        h2 = currentVal;
        if (currentVal > h1) {
            h2 = h1;
            h1 = currentVal;
        }
    }
}

感觉这样做很愚蠢且静态，但这确实有效。我应该使用排序算法吗？如果需要的话，有什么建议可行的算法呢？

- krystah

---

你使用 std::sort() 时遇到了什么问题？ - πάντα ῥεῖ

不需要排序，这样做就可以了。（虽然如果列表足够短，排序比重新发明轮子更方便） - ale64bit

由于您仅存储3个值，排序的开销可能比您的代码更长。请查看汇编语言清单。 - Thomas Matthews

Answer 1

对于"top 3"，这是完全合理的。而对于一个更大（但固定）值的“top k”，您可以尝试使用优先队列。

- rici

Answer 2

您可以通过以下方式在数组中找到任意数量的最大元素：

#include <iostream>
#include <algorithm>
#include <functional>
#include <array>

template <size_t N> 
void n_max_element( const int a[],
                    size_t n,
                    std::array<int, N> &nmax )
{
    std::partial_sort_copy( a, a + n, 
                            nmax.begin(), nmax.end(), 
                            std::greater<int>() );
}   

int main() 
{
    const size_t N = 10;
    int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    std::random_shuffle( a, a + N );

    std::array<int, 3> max;

    n_max_element( a, N, max );

    std::cout << "max[0] = " << max[0] 
              << ", max[1] = " << max[1] 
              << ", max[2] = " << max[2] << std::endl;

    return 0;
}

输出结果为：

max[0] = 9, max[1] = 8, max[2] = 7

- Vlad from Moscow