Javascript數組：算法排序和挑選

在這種情況下，我有一個0到256之間的4個整數數組，需要按升序排序。例如：Javascript數組：算法排序和挑選

[0, 12, 211, 4]當我排序，我得到（當然）：[0, 4, 12, 211]

我只是通過請求Array[0]（第一索引）

現在，我的問題是讓整數值;很多時候，數組中有相同的值。像：

[0, 0, 0, 12] // already sorted

在這些情況下我需要從最上面的相等值挑選一個隨機索引（0,0,0），其他possiblities是（後分選）：

[211, 211, 211, 255] // results in 0 OR 1 OR 2 
[13, 13, 125, 256] // results in 0 OR 1 
[4, 211, 211, 255] // results in 0 
[0, 1, 1, 4] // results in 0;

所以我需要挑選從升序排序數組的最頂層值中選擇一個隨機索引。這是在排序時完成的，還是以比很多if-elses更簡單的方式完成？

來源

2011-02-15 Caspar Kleijne

請你澄清一下你want.Pick從陣列最頂端值的隨機指數？ ?????難道當最低值被重複多次，你需要回到一切都取決於此元素出現的索引。 – Algorithmist 2011-02-15 11:39:16

@Algorithmist，確實如此。 – 2011-02-15 11:47:07

排序

如果速度是重要的（你似乎表明它），然後你看着排序網絡？我發現這些在排序小數字時非常快。

排序與排序網絡：

網絡對於N = 4，採用玻色 - 納爾遜算法。

創建日期：Tue Feb 15 04:44:06 2011 創建者：perl模塊 Algorithm :: Networksort版本1.05。 N = 4的網絡，使用Bose-Nelson 算法。輸入線。比較器大小 1.比較器大小2.此網絡中有5個比較器，將分組爲3個並行操作。

[[0,1]，[2,3]] [[0,2]，[1,3]] [[1,2]]

這在4列作圖。

僞：

if [0] > [1] { swap(0, 1) } 
if [2] > [3] { swap(2, 3) } 
if [0] > [2] { swap(0, 2) } 
if [1] > [3] { swap(1, 3) } 
if [1] > [2] { swap(1, 2) }

查找索引集

反正這個問題可以用一種鴻溝來解決和克服的（僞）：

// First index is unique 
if [0] != [1] 
    return 0 
// First 2 are equal 
else if [1] != [2] 
    return 0 or 1 
// First 3 are equal 
else if [2] != [3] 
    return 0 or 1 or 2 
// All are equal 
else 
    return 0 or 1 or 2 or 3 
end

或者你可以用一個循環做到這一點：

for i = 0 to 2 

    if [i] != [i+1] 
     return random(0 to i) 
     break loop 
    end if 

loop

你應該去的算法，這使得大多數語義感，是最簡單的了別的可能保持，除非速度是至關重要的。

來源

2011-02-15 10:30:30

製作從右環向左選擇的元素就可以了，如果是排序過程之後完成它只會增加N到複雜

改變從nlogn到nlogn + n不算多CPU昂貴。

編輯：在你的例子最上面的值相等，應該不會是：

[211, 211, 211, 255] // results in 0 OR 1 OR 2 
[13, 13, 125, 256] // results in 0 OR 1 
[4, 211, 211, 255] // results in 1 or 2 
[0, 1, 1, 4] // results in 1 or 2;

？

來源

2011-02-15 10:16:37 fmsf

這將返回相等值的隨機指數：

var myNums = new Array(211, 211, 211,211,214, 255); 
myNums = myNums.sort(); 
if(myNums.length == 0) 
    alert("Array is zero sized"); 
else 
{ 
    var smallest = myNums[0]; 
    var last=0; 
    var start = 0; 
    while(smallest == myNums[last]) 
     last++; 
    last = last-1; 
    var randIndex = Math.floor(Math.random() *(last - start + 1)+ start); 
    alert(randIndex); 
}

看到它在這裏工作： http://jsfiddle.net/rAbh3/

來源

2011-02-15 11:28:36 DhruvPathak

Javascript數組：算法排序和挑選

回答

相關問題