JavaScript：數組排序優化

Question

我有一個嵌套對象的JavaScript數組，例如：[{id:1, position: 1}, {id:2, position: 2}, {id:3, position: 3}, {id:4, position: 4}, {id:7, position: 7}, {id:5, position: 5},{id:6, position: 6}]。這只是一個例子，實際上我在我的應用程序中有一個有100個記錄的數組。我正在嘗試使用JavaScript數組排序方法對數組進行排序。讓我們說數組名是myArray的，所以我做類似如下：

myArray.sort(function(a, b) { 
    return a.position- b.position; 
}); 

它工作正常，但它的凍結我的瀏覽器。是否有任何優化的方法來進行分類。

Answer 1

您可以製作自己的非常高效的排序算法實現，如QuickSort和MergeSort。

In this interesting article您會發現javascript sort（）和MergeSort的一個實現之間的比較。我建議您閱讀更多關於sorting algorithms的文章，並找到它更適應您的問題的文章。

Answer 2

在之後的一段評論中，您提到數據一點一點地出現，而不是一次全部出現。但是Array.prototype.sort()每次都必須重新整個數組，儘管它大多已經排序;只有少數元素超出了應有的位置。

對於像你這樣的情況下，我會忍不住去與插入排序而非JavaScript內置的排序方法（通常的變種歸併排序或快速排序，取決於發動機）。 插入排序並不是很好的通用排序算法，但是當您只需將幾個項目添加到已排序的數組中時，插入排序並不是很好。這就是你在這裏做的事情，所以它聽起來很合適。

這是算法的基本實現。

/** 
* Compare two items as though they were strings. 
* 
* This is like the default comparison for Array.prototype.sort() 
* 
* @param {*} a The first item 
* @param {*} b The second item 
* 
* @return -1 if a is less, 1 is b is less, 0 otherwise 
*/ 
function compareStrings(a, b) { 
    var sa = String(a), 
     sb = String(b); 

    if (sa < sb) { 
     return -1; 
    } 
    if (sa > sb) { 
     return 1; 
    } 
    return 0; 
} 

/** 
* Insert a new item into a sorted array. 
* 
* The compareFunction callback function works as for the analogous argument 
* in Array.prototype.sort(). Leave unspecified to compare lexically. 
* 
* @param {Array}  data   A sorted array, into which to put this item 
* @param {*}   newItem   The item to add to the data. 
* @param {Function=} compareFunction Optional comparison function. 
*/ 
function arrayInsert(data, newItem, compareFunction) { 
    var stop = data.length, 
     i = 0; 

    compareFunction = compareFunction || compareStrings; 
    while (i < stop) { 
     if (compareFunction(newItem, data[i]) < 0) { 
      data.splice(i, 0, newItem); 
      return; 
     } 
     i += 1; 
    } 
    // If we got this far, then this should be the last item. 
    data.push(newItem); 
} 

整個陣列仍需要進行一次排序，頁面加載時，你不應該使用的是插入排序（這將是最好的，如果你的服務器向您發送已排序的數據，但如果你不能這樣做，那就用正常的Array.prototype.sort函數）。然後，當您獲得新數據時，請爲您獲得的每個新數據項撥打arrayInsert(data, newItem, /* your comparison function */)一次。這應該會加快速度。

如果這仍然太慢，那麼你可以把你的新數據項放入一個隊列，並在頁面中添加一個短計時器。這個計時器每隔幾毫秒檢查一次隊列，如果有任何項目在等待，它會將其中的一個添加到數組中。這實際上並不會讓事情變得更快（事實上，這會讓它們變慢一點），但是頁面不應該再凍結了。

Answer 3

我建議使用二分查找來定義在哪個索引處插入新對象，而不是推送然後排序。

由於沒有函數調用，下面的代碼沒有開銷。

此外還有一個變量iteration它只作爲一個證人，你可以把它扔掉。

我作了如下的代碼

的jsfiddle假設你a是已經排序，幷包含UNIQUE位置，你可以做到這一點

// THIS SECTION IS ONLY THERE TO SUIT YOUR CONSTRAINTS (100 objects in a) 
var a = []; 

for (var i = 0; i < 200; i++) { 
    if (i & 1) { 
     a.push({ id: i, position: i }); // objects are pushed only if they position is odd 
    } 
} 

// this means o.position (our new object) can have any even value, we know that it won't already exist in a 
var o = { 
    id: 2, 
    position: 2 
}; 
var start = 0, 
    end = (a.length - 1), 
    mid = end >>> 1, 
    left, 
    right; 

var iterations = 0; 

while (mid !== a.length - 1) { 
    if (mid > 0) { 
     leftIsMore = a[mid - 1].position > o.position; 
    } else { 
     leftIsMore = false; 
    } 

    rightIsLess = a[mid].position < o.position; 

    if (!leftIsMore && !rightIsLess) { 
     break; 
    } else if (leftIsMore) { 
     end = mid - 1; 
    } else { 
     start = mid + 1; 
    } 

    mid = (start + end) >>> 1; 
    iterations++; 
} 

var index = mid; 

if (index === a.length - 1) { 
    a.push(o); 
} else { 
    a.splice(index, 0, o); 
} 

console.log(a, 'Number of iterations to insert: ', iterations);