如何批量排序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);