c++ - 为第一个元素对数组进行排序的算法，然后是前 2 个元素，然后是前 3 个元素，依此类推

Question

我有一个未排序的数字列表，我想要一个算法，这样我可以获得第一个 R 元素的排序列表，但是由于这个 R 对于不同的测试用例可能不同，我不想每次都对第一个 R 的数组进行排序元素。有没有办法让我完成这项工作。一种可能的方法是维护 vector 数组，这样我先排序 1 个数字，然后排序前 2 个数字，然后排序前 3 个数字，依此类推，但这需要 1log1 + 2log2 + 3log3 + .... + nlogn 时间，即 N^ 2logN 复杂度。有更快的方法吗？

Answer 1

在这种情况下，旧的插入排序似乎会比 O(N^2 lg N) 做得更好，因为您不需要对元素进行排序从头开始为每个 R。假设您有 1..R-1 中 n 数组的已排序前 n 元素的拷贝。只需将第 R 元素插入到 R-1 第一个元素(即 O(R))的已排序数组的拷贝中，就可以得到已排序的数组R 第一个元素。

如果您想要 1..N 中的每个 R 的结果，那就是 O(N^2)，但这会更少在实践中比 O(N^2) 更复杂，因为您可以按需生成排序数组，从元素少于 R 的最后一个排序数组开始。