如何批量排序JS數組（

Question

）我有一個JS應用程序需要做一個複雜的大型數組，然後顯示它。使用內置的array.sort(cb)方法可能需要1秒鐘的時間才能處理我的數據。這足以讓我的用戶界面變得很笨拙。

由於用戶界面的高度足以顯示屏幕上的排序數組的子集，其餘部分位於滾動或分頁之下，因此我有一個想法。如果我製作了一個通過大型數組的算法，並且快速按照前N個項目完全排序的方式進行排序，但是數組中的其餘項不完全排序。每次運行我的算法時，它都會從上到下排列更多的數組。

因此，我可以將我的處理分解爲塊並擁有流暢的UI。在頭幾秒鐘數組不會被完美排序，但缺陷會在滾動下方，所以他們不會被注意到。

我天真的解決方案是編寫我自己的「選擇排序」，能夠在N次匹配後中斷並稍後恢復，但「選擇排序」是一個非常糟糕的算法。更快的算法（從我的理解）必須完成，以確保前N個項目是穩定的。

有沒有人知道現有的解決方案呢？我瘋了嗎？有什麼建議麼？

UPDATE

回吐@moreON提出這個想法，我寫道，撈出一旦它具有精度要求的自定義快速排序。這種數據的本地排序需要1秒。常規的QuickSort花費了大約250毫秒，這已經非常好了。在排序前100個項目後排序的QuickSort花了10毫秒，這要好得多。然後我可以再花250ms來完成排序，但這並不重要，因爲用戶已經在查看數據。這將用戶的經驗延遲從1秒減少到10毫秒，這非常好。

//Init 1 million random integers into array 
var arr1 = []; 
var arr2 = []; 
for(var i=0;i<1800000;i++) { 
    var num = Math.floor(Math.random() * 1000000); 
    arr1.push(num); 
    arr2.push(num); 
} 
console.log(arr1); 

//native sort 
console.time("native sort"); 
arr1.sort(function(a,b) { return a-b; }); 
console.timeEnd("native sort"); //1sec 
console.log(arr1); 

//quicksort sort Ref: https://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/ 
function swap(arr, a, b) { 
    var temp = arr[a]; 
    arr[a] = arr[b]; 
    arr[b] = temp; 
} 
function cmp(a,b) { 
    return (a<b); 
} 
function partition(items, left, right) { 
    var pivot = items[Math.floor((right + left)/2)]; 
    var i = left; 
    var j = right; 

    while (i <= j) { 
     while (cmp(items[i],pivot)) i++; 
     while (cmp(pivot,items[j])) j--; 
     if (i <= j) { 
     swap(items, i, j); 
     i++; 
     j--; 
     } 
    } 
    return i; 
} 
function quickSort(items, left, right, max) {  
    if(max && left-1 > max) return items; //bail out early if we have enough 
    if (items.length > 1) { 
     var index = partition(items, left, right); 
     if (left < index - 1) quickSort(items, left, index - 1, max); 
     if (index < right) quickSort(items, index, right, max); 
    } 
    return items; 
} 

//sort first 100 
console.time("partial Quicksort"); 
arr2 = quickSort(arr2,0,arr2.length-1,100); 
console.timeEnd("partial Quicksort"); //10ms 
console.log(arr2); 

//sort remainder 
console.time("finishing Quicksort"); 
arr2 = quickSort(arr2,100,arr2.length-1); //250ms 
console.timeEnd("finishing Quicksort");  
console.log(arr2); 

Answer 1

首先，對績效改善的期望有一些看法。有效的排序算法是O（N * log2（N））。對於N = 1,000,000個項目，N * log2（N）〜N * 20。我懷疑你有很多項目想要在網頁中呈現。

如果您只需渲染前25行，則選擇排序將使用N * 25來排序它們，因此假設可比較的常量開銷，它實際上會表現更差。

如果你想進一步實驗，我可以想到的一個算法是：維護PAGE_SIZE最小項目的二叉樹。不斷更新數據，在發現較小的數據時刪除最大的項目。忽略重新平衡，它會帶您N * log2（PAGE_SIZE）填充樹並呈現結果的第一頁。

Answer 2

如果你要heapify array，我相信能在O(n)時間（https://en.wikipedia.org/wiki/Binary_heap#Building_a_heap），可以提取每個N項目，被做是爲了在O(N log n)時間（n越來越小，因爲你提取）。

Answer 3

我認爲你的問題歸結爲：

如何找到在大陣

前N個元素被kindof在這裏找到答案：通過遍歷Find top N elements in an Array

這是可以解決的列表一次，只是選擇前N個元素。 Θ（n）中。

看看這裏：https://jsfiddle.net/jeeh4a8p/1/

function get_top_10(list) { 
    var top10 = new Array(10).fill(0) 
    for(i in list) { 
     var smallest_in_top10 = Math.min.apply(Math, top10) 
     if(list[i] > smallest_in_top10) { 
      top10.splice(top10.indexOf(smallest_in_top10),1) 
      top10.push(list[i]) 
     } 
    } 
    return top10 
} 

console.log(get_top_10([1,2,3,4,5,6,7,8,9,10,11,12])) 

var random_list = []; 
for (var i = 0; i < 100; i++) { 
    random_list.push(Math.round(Math.random() * 999999)) 
} 

console.log(get_top_10(random_list)) 

function sortNumber(a,b) { 
    return a - b; 
} 

Answer 4

這裏是我的解決方案的清理版本排序分批大陣，因此JS線程不口吃。在我的例子中，它需要1秒array.sort(cb)並將其變爲五個單獨的100ms操作。您需要根據您的數據智能地選擇pageSize。更多的頁面會使最後的排序花費更長的時間，更少的頁面會使批次花費更長的時間。

var BatchedQuickSort = { 
    swap: function(arr, a, b) { 
    var temp = arr[a]; 
    arr[a] = arr[b]; 
    arr[b] = temp; 
    }, 
    partition: function(items, left, right, cmp) { 
    var pivot = items[Math.floor((right + left)/2)]; 
    var i = left; 
    var j = right; 

    while (i <= j) { 
     while (cmp(items[i],pivot)<0) i++; 
     while (cmp(pivot,items[j])<0) j--; 
     if (i <= j) { 
     this.swap(items, i, j); 
     i++; 
     j--; 
     } 
    } 
    return i; 
    }, 
    sort: function(items, cmp, max, left, right) { //Ref: https://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/ 
    if (items.length > 1) { 
     left = typeof left != "number" ? 0 : left; 
     right = typeof right != "number" ? items.length - 1 : right; 
     var index = this.partition(items, left, right, cmp); 
     if (left < index - 1) this.sort(items, cmp, max, left, index - 1); 
     if (index < right && (!max || index<=max)) this.sort(items, cmp, max, index, right); 
    } 
    return items; 
    } 
} 

//Example Usage 
var arr = []; 
for(var i=0;i<2000000;i++) arr.push(Math.floor(Math.random() * 1000000)); 
function myCompare(a,b) { return a-b; } 

var pageSize = Math.floor(arr.length/5); 
var page = 1; 
var timer = window.setInterval(function() { 
    arr = BatchedQuickSort.sort(arr, myCompare, pageSize*page,pageSize*(page-1)); 
    if(page*pageSize>=arr.length) { 
    clearInterval(timer); 
    console.log("Done",arr); 
    } 
    page++; 
},1);