c++ - 排序算法面试

Question

给定一个数字范围从 1 到 100 的大数组。排序它的最佳方法是什么？

面试官强调了“范围”这个词，即数组中存在的最大数量是 100。

Answer 1

试试这个:

long result[100] = {0};

for (iterator it = vec.begin(); it != vec.end(); ++it)
{
    result[*it - 1]++;
}

因此，您将在 vector 上线性移动并计算存在的所有数字。结果你会收到你有多少个 1，你有多少个 2 等等，即它会被排序。

UPD:正如 KillianDS 所写，我的意思是 counting sort 。这是最快的。