将移动排序到结束列表

顺序唯一的数字列表（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

工作的呢？最佳方案？

来源

2014-02-16 user433342

它与哪种语言无关。 OP只需要一个算法，可以用最少的步骤完成他想要的任务。 – Ranveer

你是最初排序的列表吗？如果是的话，这是一个非常简单的问题，可以用少于“n”的步骤完成。 – Ranveer

我可以用它的索引来表示列表中的每个元素，所以是的，说它最初是按递增顺序排序的。 – user433342

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

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;  
}

这里是一个demo fiddle。如您所见，输入[1,2,9,3,4,8,5,6,7]按2次移动排序，并且完全随机的或反转的列表仍然是n-1移动。

来源

2014-02-16 13:40:16 zord

谢谢你送我正确的方向 – user433342

不客气。我对我的第一次尝试有点尴尬，所以我必须解决这个问题。 :) – zord

这里有一个算法：

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

非常直观，只要想一想。例子：

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

如果列表不按递增顺序进行排序，你总是可以通过指数映射。

来源

2014-02-16 12:51:40 Ranveer

我有点困惑，25341需要4个步骤来排序，25341 => 53412 => 54123 => 51234 => 12345.你如何在3步中排序该列表？ – user433342

我做了相反的事情。对于前面的事情，映射'2-> 1，5> 2，3-> 3，4-> 4，1-> 5'。然后你的问题变成'12345-> 51342'这需要四步。 – Ranveer

@ user433342看，它的工作原理！正如我所说的，您只能将算法应用到按升序排序的列表中。否则，您必须通过索引映射它。 – Ranveer

将移动排序到结束列表

回答

相关问题