该算法失败,因为它对列表的索引只有一个循环。
你的算法中发生的事情是这样的:
i=0 -> ["A", "B", "C", "D"] , [ 2, 3, 1, 0 ]
i=1 -> ["C", "B", "A", "D"] , [ 1, 3, 2, 0 ]
i=2 -> ["C", "D", "A", "B"] , [ 1, 0, 2, 3 ]
i=3 -> ["C", "D", "A", "B"] , [ 1, 0, 2, 3 ]
请注意,通过第一次交换,1
已就位0
并且您不会再次访问它,除非您将其交换为0
,本例中没有发生这种情况。
您的算法缺少的是一个贯穿索引子循环的内部循环。尝试更换if
by while
in rearrange
:
function rearrange(arr, ind) {
for (var i = 0, len = arr.length; i < len; i++) {
while (ind[i] !== i) {
swap(arr, i, ind[i]);
swap(ind, i, ind[i]);
}
}
}
关于复杂性的说明:虽然这是一个双循环,但复杂性不会改变,因为每次交换时,都会正确放置一个元素,并且每个元素最多读取两次(一次通过循环,一次通过 for 循环)。
证明上的注意事项:我不会在这里对这个算法做完整的证明,但我可以提供线索。如果ind
是一个置换,则所有元素都属于闭置换子循环。这while
循环确保您迭代整个循环,for
循环确保您检查每个可能的循环。