3622
правки
Изменения
м
→Алгоритм построения за O(N)
'''list<list<int>>''' bank(bucket)
'''for''' i = 0 to permutation.size
'''int''' position = (permutation[i] - 1)/(max / bucket) <font color=green>// Определяем в каком кармане должен лежать элемент</font>
'''int''' newPosition = 0
'''while''' newPosition < bank[pos].size '''and''' bank[pos][newPosition] < permutation[i] <font color=green>// идем до позиции где должен стоять элемент permutation[i] </font>
newPosition++
answer += bank[pos].size - newPosition <font color=green>// ищем сколько инверсий эленент создает в своем кармане</font>
bank[pos].insert( newPosition , permutation[i] ) <font color=green>// вставляем элемент в Карман на свою позицию </font>
'''for''' i = position + 1 to BUCKET - 1 <font color=green>// ищем сколько инверсий он создает с элементами в других карманах</font>
answer += bank[i].size
