c++ - 在O（nlogn）中对数组进行排序的第一个元素插入数？

Question

如果只允许移动数组的第一个元素，那么要对数组进行完全排序需要多少次插入？

在输出中，给出必要的插入次数以及每个元素向后移动的位置。

例如：

输入：

6
1 4 2 5 3 6

输出：

4
3 4 2 4

解释：

这是插入的顺序：

4 2 5 1 3 6
2 5 1 3 4 6
5 1 2 3 4 6
1 2 3 4 5 6

我可以在 O(n ² ) 中做到这一点，因为问题简化为找到第一个元素位于数组增加后缀中的位置。
如何在 O(nlogn) 中解决这个问题？

标签： c++arrayssorting