Мне нужен лучший алгоритм, чтобы решить эту проблему

Самая дорогая часть — это, очевидно, смещение до 100 000 элементов в вашем массиве результатов.

Если вы разделите этот массив на несколько кусков, вы можете ускорить его с помощью некоторого значительного фактора.

Если вы сказали «10 блоков» и запомнили количество элементов для каждого блока, вы выбираете правильный блок для записи в соответствии с ключом, а затем должны сдвигать элементы только для этого блока (до 10 раз меньше).

Новая проблема заключается в том, как добиться хорошего распределения чисел по кускам.

Также вы можете использовать связанный список: http://www.cplusplus.com/reference/stl/list/

Это очень эффективно при вставках, но отстой для случайного поиска. Но поиск — это просто операция чтения, поэтому поиск элементов x может быть быстрее (IDK), чем смещение элементов x в массиве.

Тогда вы можете использовать комбинированный подход и связать список с несколькими указателями, чтобы вы всегда могли искать из ближайшего.

Вот действительно хороший алгоритм наряду с необходимым кодированием на C ++:

Проблема решается с помощью того факта, что если на месте 7 есть 2, то два пустых поля
остаются до размещения 7. Итак, если 0 на 8, а 2 на 7, то обратный массив результатов выглядит
как: 8 _ _ 7 _ _ _ _.

Теперь разложение квадратного корня завершено, и вставка завершена:

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
int n, k = 0, d, r, s, sum, temp, m, diff, check = 1;
cin >> n;

d = sqrt(n) + 1;
int arr[n], result[n], indices[d], arr2[d][d], num = 1;

for (int i = 0; i < n; i++)
cin >> arr[i];               //The inversion sequence is accepted.

for (int i = 0; i < d; i++)
indices[i] = 0;              //Indices tell where to start counting from in each row.

for (r = 0; r < d; r++)
{
for (s = 0; s < d; s++)
{
arr2[r][s] = num;       //Array is filled with 1 to n (after sqrt decomposition).
num = num + 1;
if (num == n+1)
{
check = 0; break;
}
}
if (check == 0)
break;
}

int l = s;
while (l >= 0)                  //Non-Zero numbers are shifted to right and 0 placed in
{                               //empty spaces.
arr2[r][d-1 - k] = arr2[r][l];
k = k + 1; l = l - 1;
}

k = d-1 - k + 1;
for (int t = 0; t < k; t++)
arr2[r][t] = 0;

indices[r] = indices[r] + k;    //Index of the last row is shifted to first non-zero no.

for (int i = n-1; i >= 0; i--)
{
sum = 0; m = 0;
while (sum < arr[i] + 1)
{
sum = sum + (d - indices[m]); //Empty boxes in each row are counted.
m = m + 1;
}

m = m - 1;
sum = sum - (d - indices[m]);     //When sum = 1 + corresponding value in inversion
diff = arr[i] + 1 - sum;          //sequence, then that particular value is made 0
temp = indices[m] + diff - 1;     //and (that value - 1) is the index of the number
//to be placed in result array.
result[arr2[m][temp] - 1] = i+1;
for (int w = temp - 1; w >= indices[m]; w--)
{
arr2[m][w + 1] = arr2[m][w];  //Then, 0 is shifted to just before non-zero number
}                                 //in the row, and the elements are shifted right
arr2[m][indices[m]] = 0;          //to complete the sort.
indices[m] = indices[m] + 1;
}                                     //This is done n times for 1 to n integers thus
//giving the permutation in reverse order in result
for (int p = n-1; p >= 0; p--)        //array.
cout << result[p] << ' ';

return 0;
}

Ваш алгоритм неэффективен для этой проблемы, потому что ваша сложность O (n ^ 2), что означает 10 ^ 10 операций для некоторых входных случаев. Вы должны найти решение, которое дешевле.

Я предлагаю вам следующий алгоритм (индексы от 1 до N):

for i=1 to N
input a(i)
if i==1 insert 1 into b
else insert i into b at place i-a(i)
end