將移動排序到結束列表

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

將移動排序到結束列表

回答

相關問題