对移动到结束列表进行排序

Question

一个连续的唯一数字列表（1,2,3,...,n）已被随机化，我需要通过一次将一个项目移动到列表的末尾来对其进行排序。 哪种算法将提供最少的移动次数？

注意：[123645] 可以排序 1 步，[125346] 在 2 步中排序，[654321] 需要 5 步。 我想要一种可以解释这些的算法，而不是一直给我 n-1 的算法。

我能想到的最好的：

for(var x=1; x<=list.length; x++)
if indexOf(x+1)<indexOf(x) then move x+1 to end

这行得通吗？ 最佳解决方案？

Answer 1

这是一个算法：

1. 检查列表的长度（从开始）直到它增加，即在列表开始减少时停止。
2. 从列表长度中减去该长度。这就是你的答案。

很直观，想想就知道了。例：

12345 -> 25341
|25| is in increasing order and after that it becomes decreasing.
Length (2,5) = 2
Answer = 5 - 2 = 3

如果列表未按递增顺序排序，则始终可以通过索引映射它。

Answer 2

这是我的第二个解决方案：

function mysort(array) {
    var index, value, badValues,
        len = array.length;
    // find values at a bad place
    badValues = [];
    for (index = 0; index < len; index++) {
        if (array[index] !== index + 1 - badValues.length) {
            badValues.push(array[index]);
        }
    }    
    // move those to the end in increasing order
    while (badValues.length > 0) {
        // minimum bad value
        value = Math.min.apply(null, badValues);
        index = array.indexOf(value);        
        // move to the end
        array.splice(index, 1);
        array.push(value);
        // one bad solved
        badValues.splice(badValues.indexOf(value), 1);    
    }
    return array;    
}

这是一个演示小提琴。如您所见，输入[1,2,9,3,4,8,5,6,7]按 2 个移动排序，并且完全随机或反向列表仍然是n-1移动。