javascript - 如何对一个JS数组进行批量排序(为了性能)

Question

我有一个 JS 应用程序需要对一个大数组进行复杂的排序然后显示它。使用内置的 array.sort(cb) 方法处理我的数据最多可能需要 1 秒。这足以让我的 UI 变得卡顿。

因为 UI 的高度仅足以在屏幕上显示已排序数组的一个子集，而其余部分位于滚动条下方或已分页，所以我有了一个想法。如果我创建一个遍历大型数组的算法并快速排序，使得前 N 项完全排序，但数组中的其余项排序不完全，会怎样？每次我运行我的算法时，它都会从上到下对数组进行更多排序。

这样我就可以将我的处理分解成 block 并拥有流畅的用户界面。在最初的几秒钟内，数组不会被完美排序，但缺陷会在滚动条下方，因此不会被注意到。

我天真的解决方案是编写我自己的“选择排序”，能够在 N 次匹配后中断并稍后恢复，但“选择排序”是一个非常糟糕的算法。更快的算法(根据我的理解)必须完成以保证前 N 项是稳定的。

有人知道现有的解决方案吗？我疯了吗？有什么建议吗？

更新

采用@moreON 建议的想法，我编写了一个自定义 QuickSort，一旦它具有所需的精度就会退出。 native 排序为此数据花费了 1 秒。常规的 QuickSort 花费了大约 250 毫秒，这已经好得惊人了。在对前 100 个项目进行排序后退出的 QuickSort 花费了 10 毫秒，这要好得多。然后我可以再花 250 毫秒来完成排序，但这并不重要，因为用户已经在查看数据。这将用户体验到的延迟从 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) 时间内完成(https://en.wikipedia.org/wiki/Binary_heap#Building_a_heap)，您可以提取每个N 个项目，按顺序，在 O(N log n) 时间内(n 在提取时变小)。