25
правок
Изменения
Нет описания правки
'''for''' i = 1..n
'''for''' j = 1..(i - 1)
'''if''' P}[j] > P}[i]
T[P[i]] = T[P[i]]++
Сложность данного алгоритма {{---}} <tex>O(n^2)</tex>. Уменьшить время работы можно используя алгоритм, похожий на [[Сортировка_слиянием |сортировку слиянием.]]
<font color=green>// ''inverses_merge'' {{---}} процедура, сливающая два списка пар</font>
<font color=green>// ''inverses_get'' {{---}} процедура, рекурсивно получающая таблицу инверсий для перестановки</font>
'''def''' inverses_merge(ls1, ls2)}:
result = []
it1, it2 = ''null''
'''while''' (it1 < ls1.length) '''and''' (it2 < ls2.length):
'''if''' ls1[it1}].item < ls2[it2].item:
result.append(ls1[it1])
it1++
'''else:'''
result.append(item = ls2[it2].item, inverses = ls2[it2].inverses + ls1.length - it1)
it2++
'''while''' it1 < ls1.length):
result.append(ls1[it1])
it1++
'''while''' (it2 < ls2.length):
result.append(ls2[it2])
it2++
'''return''' result
'''def''' inverses_get(ls)}:
'''if''' ls.length == 1
'''return''' [(item = ls[0], inverses = 0)]
'''else:'''
'''return''' inverses_merge(inverses_get(ls.first_half), inverses_get(ls.second_half))
result = array(0, n)
curr = 1
'''for''' k '''in''' ls:
j = 0
'''for''' i= 0..(n- 1)
'''if''' result[i] == 0
'''if''' j == k
result = array(n)
curr = 1
'''for''' k '''in''' inv
node = tree.root
'''while''' !node.is_leaf
'''if''' k < node.left.value
node = node.left
'''else:'''
k -= node.left.value
node = node.right
