Array.sort不同瀏覽器中的排序穩定性

Array.sort在不同瀏覽器中的穩定性如何？我知道ECMA腳本規範沒有指定使用哪種算法，也沒有指定排序是否應該穩定。Array.sort不同瀏覽器中的排序穩定性

我在Firefox的 https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Global_Objects/Array/sort 中發現了這個信息，它指定firefox使用穩定的排序。

有沒有人知道IE 6/7/8，Chrome，Safari？

來源

2010-06-11 Boushley

Simple test case（忽略標題，如果發動機的排序穩定，第二組數字應該是連續的）。

只要我使用過IE（IE6），它的排序一直很穩定。在IE8中再次檢查，它似乎仍然是這種情況。

儘管您鏈接到的Mozilla頁面說Firefox的排序是穩定的，但我絕對認爲Firefox 2.0之前並不總是這種情況。

一些粗略結果：

IE6 +：穩定
火狐< 3：不穩定
火狐> = 3：穩定
鉻< = 5（即，所有版本到目前爲止）：不穩定
歌劇< 10：不穩定
歌劇院> = 10：穩定
的Safari 4：穩定

在Windows上的所有測試。

參見：

Fast stable sorting algorithm implementation in javascript

來源

2010-06-12 06:14:51

保持此更新會很有用。 – ColBeseder 2012-07-26 07:48:17

看起來像Chrome（V8）將保持這種方式：http://code.google.com/p/v8/issues/detail?id=90 – 2012-10-19 13:06:08

http://ofb.net/~sethml/is-sort-stable .html？（爲了以防萬一，我將它保存在網絡存檔中） – Pierre 2014-01-21 16:44:09

-2

如果您正在尋找瀏覽器列表，您應該使用非本機排序算法，我的建議是不要。

而是在腳本加載並做出決定時進行排序正確性檢查。

由於規範在這方面不需要特定的行爲，即使在同一瀏覽器行內，它也不會影響以後的更改。

您可以提交一個補丁到http://www.browserscope.org/以在其套件中包含這些測試。但是，功能檢測再次優於瀏覽器檢測。

來源

2010-06-11 23:04:42 unomi

我不知道，如果你可以寫一個全面的檢查，來確保一個穩定的排序。它可能在一瞬間看起來很穩定，但接下來會變得不穩定。例如，如果按某種方式排序依賴於內存中JavaScript對象的位置，這可能會發生 - 這可能是不可預測的。 – 2012-04-06 01:38:35

@RichDougherty - 我相信你*無法*。您無法通過運行來證明排序算法是穩定的！這就像試圖證明一輛汽車在該區域駕駛一次是可靠的。你必須分析算法和實現。 – Malvolio 2012-07-21 15:16:12

@Malvolio，我想我們同意。我在說，如果一個測試現在通過，那麼它肯定不能保證在未來通過，因此做一個負載時間檢查穩定性是徒勞的。 – 2012-12-11 10:39:47

我想分享一個我經常在C/C++中用於qsort()的技巧。

JS'sort（）允許指定一個比較函數。創建具有相同長度的第二陣列和從0

function stableSorted(array, compareFunction) { 
    compareFunction = compareFunction || defaultCompare; 
    var indicies = new Array(array.length); 
    for (var i = 0; i < indicies.length; i++) 
    indicies[i] = i;

這是索引爲原始陣列隨着數字填充它。我們要排序第二個數組。進行自定義比較功能。

indicies.sort(function(a, b)) {

它會得到第二陣列的兩個元素：使用它們作爲索引到原始陣列和比較的元素。

var aValue = array[a], bValue = array[b]; 
    var order = compareFunction(a, b); 
    if (order != 0) 
     return order;

如果元素恰好相等，則比較它們的索引以使訂單穩定。

if (a < b) 
    return -1; 
    else 
    return 1; 
    });

排序（）之後，第二個數組將包含您可以使用訪問穩定原始數組中的元素進行排序次序索引。

var sorted = new Array(array.length); 
    for (var i = 0; i < sorted.length; i++) 
    sorted[i] = array[indicies[i]]; 
    return sorted; 
} 

// The default comparison logic used by Array.sort(), if compareFunction is not provided: 
function defaultCompare(a, b) { 
    a = String(a); 
    b = String(b); 
    if (a < b) return -1; 
    else if (a > b) return 1; 
    else return 0; 
}

一般來說，穩定的排序算法只有成熟，並且仍然需要比良好的qsort更多的額外內存。我想這就是爲什麼很少有規格要求穩定排序的原因。

來源

2010-06-11 23:10:18 Dummy00001

Array.sort不同瀏覽器中的排序穩定性

回答

相關問題